# 使用整数算术可以实现按位运算符吗？

• 加法c = a + b
• 减法c = a – b
• 分部c = a / b
• 乘法c = a * b
• 模量c = a％b
• 最小值c = min（a，b）
• 最大值c = max（a，b）
• 比较c =（a <b），c =（a == b），c =（a <= b），et.c.
• 跳转跳转，等等

• 或者c = a | b
• c = a＆b
• XORC = A ^ B
• 左移c = a << b
• 右移c = a >> b
• （所有的整数都被签名，所以这是一个问题）
• 签字转换c = a >>> b
• 补的a =〜b
• （已经find了解决办法，见下文）

## 有些想法可能有帮助：

``// Bitwise one's complement b = ~a; // Arithmetic one's complement b = -1 - a;` `

` `// Bitwise left shift b = a << 4; // Arithmetic left shift b = a * 16; // 2^4 = 16 // Signed right shift b = a >>> 4; // Arithmetic right shift b = a / 16;` `

` `b = 1; switch (a) { case 15: b = b * 2; case 14: b = b * 2; // ... exploting fallthrough (instruction memory is magnitudes larger) case 2: b = b * 2; case 1: b = b * 2; }` `

` `switch (a) { case 15: b = 32768; break; case 14: b = 16384; break; // ... exploiting the fact that a jump is faster than one additional mul // at the cost of doubling the instruction memory footprint. case 2: b = 4; break; case 1: b = 2; break; }` `

### 5 Solutions collect form web for “使用整数算术可以实现按位运算符吗？”

` `// table used for shift operations powtab = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, -32768 }; // logical shift left if (shift > 15) { a = 0; // if shifting more than 15 bits to the left, value is always zero } else { a *= powtab[shift]; } // logical shift right (unsigned) if (shift > 15) { a = 0; // more than 15, becomes zero } else if (shift > 0) { if (a < 0) { // deal with the sign bit (15) a += -32768; a /= powtab[shift]; a += powtab[15 - shift]; } else { a /= powtab[shift]; } } // arithmetic shift right (signed) if (shift >= 15) { if (a < 0) { a = -1; } else { a = 0; } } else if (shift > 0) { if (a < 0) { // deal with the sign bit a += -32768; a /= powtab[shift]; a -= powtab[15 - shift]; } else { // same as unsigned shift a /= powtab[shift]; } }` `

` `// XOR (^) c = 0; for (x = 0; x <= 15; ++x) { c += c; if (a < 0) { if (b >= 0) { c += 1; } } else if (b < 0) { c += 1; } a += a; b += b; } // AND (&) c = 0; for (x = 0; x <= 15; ++x) { c += c; if (a < 0) { if (b < 0) { c += 1; } } a += a; b += b; } // OR (|) c = 0; for (x = 0; x <= 15; ++x) { c += c; if (a < 0) { c += 1; } else if (b < 0) { c += 1; } a += a; b += b; }` `

` `if (a & 16) becomes if ((a % 32) > 15) a &= 16 becomes if ((a % 32) < 15) a += 16` `

` `#include <stdint.h> #include <stdio.h> #include <stdlib.h> #define XOR(a,b) (a + b - 2*AND(a,b)) #define IOR(a,b) XOR(XOR(a,b),AND(a,b)) // Credit to Jan Gray, Gray Research LLC, for IOR static const uint16_t andlookup[256] = { #define C4(a,b) ((a)&(b)), ((a)&(b+1)), ((a)&(b+2)), ((a)&(b+3)) #define L(a) C4(a,0), C4(a,4), C4(a,8), C4(a,12) #define L4(a) L(a), L(a+1), L(a+2), L(a+3) L4(0), L4(4), L4(8), L4(12) #undef C4 #undef L #undef L4 }; uint16_t AND(uint16_t a, uint16_t b) { uint16_t r=0, i; for ( i = 0; i < 16; i += 4 ) { r = r/16 + andlookup[(a%16)*16+(b%16)]*4096; a /= 16; b /= 16; } return r; } int main( void ) { uint16_t a = 0, b = 0; do { do { if ( AND(a,b) != (a&b) ) return printf( "AND error\n" ); if ( IOR(a,b) != (a|b) ) return printf( "IOR error\n" ); if ( XOR(a,b) != (a^b) ) return printf( "XOR error\n" ); } while ( ++b != 0 ); if ( (a & 0xff) == 0 ) fprintf( stderr, "." ); } while ( ++a != 0 ); return 0; }` `

YOu也可以使用加法，减法和> =操作来完成所有的事情。 每个按位操作都可以使用macros展开成这样的东西：

` `/*I didn't actually compile/test it, it is just illustration for the idea*/ uint16 and(uint16 a, uint16 b){ uint16 result = 0; #define AND_MACRO(c) \ if (a >= c){ \ if (b >= c){\ result += c;\ b -= c;\ }\ a -= c;\ }\ else if (b >= c)\ b -= c; AND_MACRO(0x8000) AND_MACRO(0x4000) AND_MACRO(0x2000) AND_MACRO(0x1000) AND_MACRO(0x0800) AND_MACRO(0x0400) AND_MACRO(0x0200) AND_MACRO(0x0100) AND_MACRO(0x0080) AND_MACRO(0x0040) AND_MACRO(0x0020) AND_MACRO(0x0010) AND_MACRO(0x0008) AND_MACRO(0x0004) AND_MACRO(0x0002) AND_MACRO(0x0001) #undef AND_MACRO return result; }` `

` `include <limits.h> const int BITWIDTH = CHAR_BIT; typedef int[BITWIDTH] bitpattern; // fill bitpattern with base-2 representation of n // we used an lsb-first (little-endian) representation void base2(char n, bitpattern array) { for( int i = 0 ; i < BITWIDTH ; ++i ) { array[i] = n % 2 ; n /= 2 ; } } void bitand( bitpattern op1, bitpattern op2, bitpattern result ) { for( int i = 0 ; i < BITWIDTH ; ++i ) { result[i] = op1[i] * op2[i]; } } void bitor( bitpattern op1, bitpattern op2, bitpattern result ) { for( int i = 0 ; i < BITWIDTH ; ++i ) { result[i] = (op1[i] + op2[i] != 0 ); } } // assumes compiler-supplied bool to int conversion void bitxor( bitpattern op1, bitpattern op2, bitpattern result ) { for( int i = 0 ; i < BITWIDTH ; ++i ) { result[i] = op1[i] != op2[i] ; } }` `
• 将N维值映射到希尔伯特曲线上的点
• algorithm来检测圆与相同平面中的任何其他圆相交
• 以独特而确定的方式将两个整数映射到一个整数
• 我如何检查Python中的NaN？
• Javascript，^（插入符号）操作符做什么？
• 为什么Math.floor返回一个double？
• 为什么在标准C ++库中不是int pow（int base，int exponent）？
• 将数字除以3，不使用*，/，+， - ，％运算符
• 我怎样才能写一个权力函数呢？
• 为什么不能用LR（1）parsing器分析C ++？
• 如何在PHP中不用余数来分割数字？