Viv*_*rma 52 c c++ algorithm bit-manipulation
如何在不使用++或+或任何其他算术运算符的情况下添加两个数字？
这是一个很久以前在一些校园采访中提出的问题.无论如何,今天有人问了一些有关操作的问题,并且在答案中提到了一个美丽的斯坦福钻头.我花了一些时间研究它,并认为实际上可能有一个问题的答案.我不知道,我找不到一个.答案是否存在？
Jas*_*ton 96
这是我前一段时间为了好玩而写的.它使用二进制补码表示,并使用进位的重复移位实现加法,主要在加法方面实现其他运算符.
#include <stdlib.h> /* atoi() */
#include <stdio.h> /* (f)printf */
#include <assert.h> /* assert() */
int add(int x, int y) {
int carry = 0;
int result = 0;
int i;
for(i = 0; i < 32; ++i) {
int a = (x >> i) & 1;
int b = (y >> i) & 1;
result |= ((a ^ b) ^ carry) << i;
carry = (a & b) | (b & carry) | (carry & a);
}
return result;
}
int negate(int x) {
return add(~x, 1);
}
int subtract(int x, int y) {
return add(x, negate(y));
}
int is_even(int n) {
return !(n & 1);
}
int divide_by_two(int n) {
return n >> 1;
}
int multiply_by_two(int n) {
return n << 1;
}
int multiply(int x, int y) {
int result = 0;
if(x < 0 && y < 0) {
return multiply(negate(x), negate(y));
}
if(x >= 0 && y < 0) {
return multiply(y, x);
}
while(y > 0) {
if(is_even(y)) {
x = multiply_by_two(x);
y = divide_by_two(y);
} else {
result = add(result, x);
y = add(y, -1);
}
}
return result;
}
int main(int argc, char **argv) {
int from = -100, to = 100;
int i, j;
for(i = from; i <= to; ++i) {
assert(0 - i == negate(i));
assert(((i % 2) == 0) == is_even(i));
assert(i * 2 == multiply_by_two(i));
if(is_even(i)) {
assert(i / 2 == divide_by_two(i));
}
}
for(i = from; i <= to; ++i) {
for(j = from; j <= to; ++j) {
assert(i + j == add(i, j));
assert(i - j == subtract(i, j));
assert(i * j == multiply(i, j));
}
}
return 0;
}
Tom*_*eys 51
或者,而不是Jason的按位方法,您可以并行计算多个位 - 对于大数字,这应该运行得更快.在每个步骤中找出携带部分和总和的部分.您尝试将进位添加到总和,这可能导致再次进位 - 因此循环.
>>> def add(a, b):
while a != 0:
# v carry portion| v sum portion
a, b = ((a & b) << 1), (a ^ b)
print b, a
return b
当你添加1和3时,两个数字都设置了1位,因此1 + 1的总和.下一步,你加2到2,并进入正确的四和.这导致退出
>>> add(1,3)
2 2
4 0
4
或者更复杂的例子
>>> add(45, 291)
66 270
4 332
8 328
16 320
336
编辑: 要使其能够轻松处理签名号码,您需要在a和b上引入上限
>>> def add(a, b):
while a != 0:
# v carry portion| v sum portion
a, b = ((a & b) << 1), (a ^ b)
a &= 0xFFFFFFFF
b &= 0xFFFFFFFF
print b, a
return b
试试
add(-1, 1)
看到一个比特在整个范围内传播并溢出超过32次迭代
4294967294 2
4294967292 4
4294967288 8
...
4294901760 65536
...
2147483648 2147483648
0 0
0L
小智 20
int Add(int a, int b)
{
while (b)
{
int carry = a & b;
a = a ^ b;
b = carry << 1;
}
return a;
}
好吧,用布尔运算符实现等价是非常简单的:你做一个逐位求和(这是一个XOR),带进位(这是一个AND).像这样:
int sum(int value1, int value2)
{
int result = 0;
int carry = 0;
for (int mask = 1; mask != 0; mask <<= 1)
{
int bit1 = value1 & mask;
int bit2 = value2 & mask;
result |= mask & (carry ^ bit1 ^ bit2);
carry = ((bit1 & bit2) | (bit1 & carry) | (bit2 & carry)) << 1;
}
return result;
}
你已经得到了一些操作答案.这是不同的东西.
在C中arr[ind] == *(arr + ind).这让我们做了一些有点令人困惑(但合法)的事情int arr = { 3, 1, 4, 5 }; int val = 0[arr];.
因此,我们可以定义一个自定义添加函数(没有明确使用算术运算符):
unsigned int add(unsigned int const a, unsigned int const b)
{
/* this works b/c sizeof(char) == 1, by definition */
char * const aPtr = (char *)a;
return (int) &(aPtr[b]);
}
或者,如果我们要避免这一招,如果用算术运算符它们包括|,&和^(这么直接的位操作是不允许的),我们可以通过查找表做到这一点:
typedef unsigned char byte;
const byte lut_add_mod_256[256][256] = {
{ 0, 1, 2, /*...*/, 255 },
{ 1, 2, /*...*/, 255, 0 },
{ 2, /*...*/, 255, 0, 1 },
/*...*/
{ 254, 255, 0, 1, /*...*/, 253 },
{ 255, 0, 1, /*...*/, 253, 254 },
};
const byte lut_add_carry_256[256][256] = {
{ 0, 0, 0, /*...*/, 0 },
{ 0, 0, /*...*/, 0, 1 },
{ 0, /*...*/, 0, 1, 1 },
/*...*/
{ 0, 0, 1, /*...*/, 1 },
{ 0, 1, 1, /*...*/, 1 },
};
void add_byte(byte const a, byte const b, byte * const sum, byte * const carry)
{
*sum = lut_add_mod_256[a][b];
*carry = lut_add_carry_256[a][b];
}
unsigned int add(unsigned int a, unsigned int b)
{
unsigned int sum;
unsigned int carry;
byte * const aBytes = (byte *) &a;
byte * const bBytes = (byte *) &b;
byte * const sumBytes = (byte *) ∑
byte * const carryBytes = (byte *) &carry;
byte const test[4] = { 0x12, 0x34, 0x56, 0x78 };
byte BYTE_0, BYTE_1, BYTE_2, BYTE_3;
/* figure out endian-ness */
if (0x12345678 == *(unsigned int *)test)
{
BYTE_0 = 3;
BYTE_1 = 2;
BYTE_2 = 1;
BYTE_3 = 0;
}
else
{
BYTE_0 = 0;
BYTE_1 = 1;
BYTE_2 = 2;
BYTE_3 = 3;
}
/* assume 4 bytes to the unsigned int */
add_byte(aBytes[BYTE_0], bBytes[BYTE_0], &sumBytes[BYTE_0], &carryBytes[BYTE_0]);
add_byte(aBytes[BYTE_1], bBytes[BYTE_1], &sumBytes[BYTE_1], &carryBytes[BYTE_1]);
if (carryBytes[BYTE_0] == 1)
{
if (sumBytes[BYTE_1] == 255)
{
sumBytes[BYTE_1] = 0;
carryBytes[BYTE_1] = 1;
}
else
{
add_byte(sumBytes[BYTE_1], 1, &sumBytes[BYTE_1], &carryBytes[BYTE_0]);
}
}
add_byte(aBytes[BYTE_2], bBytes[BYTE_2], &sumBytes[BYTE_2], &carryBytes[BYTE_2]);
if (carryBytes[BYTE_1] == 1)
{
if (sumBytes[BYTE_2] == 255)
{
sumBytes[BYTE_2] = 0;
carryBytes[BYTE_2] = 1;
}
else
{
add_byte(sumBytes[BYTE_2], 1, &sumBytes[BYTE_2], &carryBytes[BYTE_1]);
}
}
add_byte(aBytes[BYTE_3], bBytes[BYTE_3], &sumBytes[BYTE_3], &carryBytes[BYTE_3]);
if (carryBytes[BYTE_2] == 1)
{
if (sumBytes[BYTE_3] == 255)
{
sumBytes[BYTE_3] = 0;
carryBytes[BYTE_3] = 1;
}
else
{
add_byte(sumBytes[BYTE_3], 1, &sumBytes[BYTE_3], &carryBytes[BYTE_2]);
}
}
return sum;
}
所有算术运算都分解为按位运算,以便在电子设备中实现,使用NAND,AND,OR等门.
小智 5
对于无符号数,使用与在第一类中学习的相同的加法算法,但是对于基数2而不是基数10.对于3 + 2(基数10)的示例,即基数2中的11 + 10:
1 ‹--- carry bit
0 1 1 ‹--- first operand (3)
+ 0 1 0 ‹--- second operand (2)
-------
1 0 1 ‹--- total sum (calculated in three steps)