友人と私は頭の体操を行ったり来たりしていますが、これを解決する方法がわかりません。私の仮定では、一部のビット演算子で可能ですが、確かではありません。
24 に答える
Cでは、ビット演算子を使用します。
#include<stdio.h>
int add(int x, int y) {
int a, b;
do {
a = x & y;
b = x ^ y;
x = a << 1;
y = b;
} while (a);
return b;
}
int main( void ){
printf( "2 + 3 = %d", add(2,3));
return 0;
}
XOR(x ^ y
)はキャリーなしの加算です。 (x & y)
各ビットからのキャリーアウトです。 (x & y) << 1
各ビットへの持ち込みです。
ループは、すべてのビットのキャリーがゼロになるまでキャリーを追加し続けます。
int add(int a, int b) {
const char *c=0;
return &(&c[a])[b];
}
いいえ+そうですか?
int add(int a, int b)
{
return -(-a) - (-b);
}
「最良」を定義します。これがPythonバージョンです:
len(range(x)+range(y))
実行リストの+
連結であり、追加ではありません。
CMS の add() 関数は美しいです。単項否定 (非ビット演算、加算を使用するのと同じです: -y==(~y)+1) によって汚されるべきではありません。したがって、同じビット単位のみの設計を使用した減算関数を次に示します。
int sub(int x, int y) {
unsigned a, b;
do {
a = ~x & y;
b = x ^ y;
x = b;
y = a << 1;
} while (a);
return b;
}
浮気。あなたは数を否定し、最初からそれを引くことができます:)
それができない場合は、バイナリ加算器がどのように機能するかを調べてください。:)
編集:ああ、私が投稿した後にあなたのコメントを見ました。
バイナリ加算の詳細はこちらです。
これは、リップルキャリー加算器と呼ばれる加算器の場合であり、動作しますが、最適には機能しないことに注意してください。ハードウェアに組み込まれているほとんどのバイナリ加算器は、キャリールックアヘッド加算器などの高速加算器の形式です。
私のリップルキャリー加算器は、carry_inを0に設定すると、符号なし整数と2の補数整数の両方で機能し、carry_inを1に設定すると、1の補数整数で機能します。また、加算時にアンダーフローまたはオーバーフローを示すフラグを追加しました。
#define BIT_LEN 32
#define ADD_OK 0
#define ADD_UNDERFLOW 1
#define ADD_OVERFLOW 2
int ripple_add(int a, int b, char carry_in, char* flags) {
int result = 0;
int current_bit_position = 0;
char a_bit = 0, b_bit = 0, result_bit = 0;
while ((a || b) && current_bit_position < BIT_LEN) {
a_bit = a & 1;
b_bit = b & 1;
result_bit = (a_bit ^ b_bit ^ carry_in);
result |= result_bit << current_bit_position++;
carry_in = (a_bit & b_bit) | (a_bit & carry_in) | (b_bit & carry_in);
a >>= 1;
b >>= 1;
}
if (current_bit_position < BIT_LEN) {
*flags = ADD_OK;
}
else if (a_bit & b_bit & ~result_bit) {
*flags = ADD_UNDERFLOW;
}
else if (~a_bit & ~b_bit & result_bit) {
*flags = ADD_OVERFLOW;
}
else {
*flags = ADD_OK;
}
return result;
}
最初の数字を2番目の数字と同じくらい頻繁に増やしてみませんか?
ADDがビット単位の演算の組み合わせとしてではなく、単一の命令としてアセンブラに実装される理由は、実行が難しいためです。特定の下位ビットから次の上位ビットへのキャリーについて心配する必要があります。これは、マシンがハードウェアで高速に実行することですが、Cを使用しても、ソフトウェアで高速に実行することはできません。
2つの整数を追加することはそれほど難しくありません。オンラインでのバイナリ加算の例はたくさんあります。
さらに難しい問題は浮動小数点数です!http://pages.cs.wisc.edu/~smoler/x86text/lect.notes/arith.flpt.htmlに例があります
ビットシフトと AND 演算を使用して実行できます。
#include <stdio.h>
int main()
{
unsigned int x = 3, y = 1, sum, carry;
sum = x ^ y; // Ex - OR x and y
carry = x & y; // AND x and y
while (carry != 0) {
carry = carry << 1; // left shift the carry
x = sum; // initialize x as sum
y = carry; // initialize y as carry
sum = x ^ y; // sum is calculated
carry = x & y; /* carry is calculated, the loop condition is
evaluated and the process is repeated until
carry is equal to 0.
*/
}
printf("%d\n", sum); // the program will print 4
return 0;
}
C# でこの問題に取り組んでいましたが、すべてのテスト ケースに合格することができませんでした。次に、これに出くわしました。
C# 6 での実装は次のとおりです。
public int Sum(int a, int b) => b != 0 ? Sum(a ^ b, (a & b) << 1) : a;
これは、Python での私の実装です。バイト数(またはビット数)がわかっている場合は、うまく機能します。
def summ(a, b):
#for 4 bytes(or 4*8 bits)
max_num = 0xFFFFFFFF
while a != 0:
a, b = ((a & b) << 1), (a ^ b)
if a > max_num:
b = (b&max_num)
break
return b
Python コード: (1)
add = lambda a,b : -(-a)-(-b)
「-」演算子でラムダ関数を使用する
(2)
add= lambda a,b : len(list(map(lambda x:x,(i for i in range(-a,b)))))