http://blog.csdn.net/morewindows/article/details/7354571
变换符号只需要取反后加1即可
要压缩素数表的空间占用，可以使用位操作
http://segmentfault.com/a/1190000003789802
http://brokendreams.iteye.com/blog/2084088
要求不用加减符号(包括负号)来实现加减法。
第1位的值有4种，0+0=0、1+0=1、0+1=1、1+1=0，这正好符合“异或”的情况。
第2位的值来自于第一位的进位加上本身的值，进位的情况也有4种，0+0=0、1+0=0、0+1=0,1+1=1，这正好符合“与”的情况。
考虑一般性，a+b就等同于a^b + (a&b) << 1，而这又是一个加法，可递归求解，出口就是当进位为0的时候。
那么减法怎么搞呢？减法也能用加法表示嘛，比如a-b就等于a+(-b)，但不能出现负号，我们知道Java中整型数值编码方式为补码，所以一个数对应的负数就这个数“取反加1”，
1. Multiply a number by a power of two using bit left shift
1. Turning a bit off without affecting other bits
再准备面试的时候总结了一下关于bit manipulation可能用到的东西。在这里和大家分享一下～
x ^ 0s = x x & 0s = 0 x | 0s = x
x ^ 1s = ~x x & 1s = x x | 1s = 1s
x ^ x = 0 x & x = x x | x = x
boolean getBit(int i, int num){
return ( (num & (1 << i)) != 0 );
}
int setBit(int i, int num){
return num | (1 << i);
}
int clearBit(int num, int i) {
int mask = ~(1 << i);
return num & mask;
}
int clearBitMSBthroughI(int num, int i){
int mask = (1<< i) -1;
return num & mask;
}
int clearBitsIThrough0(int i, int num) {
int mask = ~( (1 << (i+1) ) -1 );
return num & mask;
}
int updateBit(int i, int num, int v){
int mask = ~(1 << i);
return (num & mask) | (v << i);
}
http://blog.csdn.net/earthma/article/details/46762943
变换符号只需要取反后加1即可
- int SignReversal(int a)
- {
- return ~a + 1;
- }
- int my_abs(int a)
- {
- int i = a >> 31;
- return i == 0 ? a : (~a + 1);
- }
- int my_abs(int a)
- {
- int i = a >> 31;
- return ((a ^ i) - i);
- }
要压缩素数表的空间占用，可以使用位操作
http://segmentfault.com/a/1190000003789802
> 不用额外的变量实现两个数字互换。
def swap(num_1, num_2):
num_1 ^= num_2
num_2 ^= num_1
num_1 ^= num_2
return num_1, num_2
证明很简单，我们只需要明白异或运算满足下面规律：
- 0^a = a;
- a^a = 0;
- a^b^c = a^c^b;
巧妙运用异或可以高效解决很多问题，比如 找出数组中只出现了一次的数（除了一个数只出现一次外，其他数都是出现两次），以及它的升级版：数组中只出现1次的两个数字(百度面试题)。
> 不用判断语句来实现求绝对值。
def bit_abs(num):
negative = num >> 31
return (num ^ negative) - negative
这里假设程序运行环境中操作系统为32位，int型整数(不考虑整数溢出)用32位存储，因此可以用
num>>31 取出符号位，后面的部分留给大伙证明。Divide two integers without using multiplication, division and mod operator.
就是说不用
乘法，除法，求模运算来实现两个整数相除，看起来很简单，我可以用除数减去被除数，直到除数小于被除数，记录减法操作的次数即可。假设是计算m/n，那么时间复杂度为O(m/n)。用Python实现后，Time Limit Exceeded。我们考虑有没有更加优化的算法呢？
我们对除数减去被除数的过程稍作改进。假设求m/n，我们不一次次的 m-n，而是找到n的一个倍数，使得m-x*n尽可能小，这样能减少循环减法的次数，进而提高效率。我们知道在按位操作中，n << k相当于 n * 2^k，因此可以用2^k 来找合适的x。
我们需要这样的一个数字k，它使得n 2^k < m < n 2^(k+1)， 然后用m - n*2^k，得到新的m'。再找相应的k'，做减法，如此循环即可
要求不用加减符号(包括负号)来实现加减法。
第1位的值有4种，0+0=0、1+0=1、0+1=1、1+1=0，这正好符合“异或”的情况。
第2位的值来自于第一位的进位加上本身的值，进位的情况也有4种，0+0=0、1+0=0、0+1=0,1+1=1，这正好符合“与”的情况。
考虑一般性，a+b就等同于a^b + (a&b) << 1，而这又是一个加法，可递归求解，出口就是当进位为0的时候。
- public static int add(int a, int b){
- return b == 0 ? a : add(a ^ b ,(a & b) << 1);
- }
那么减法怎么搞呢？减法也能用加法表示嘛，比如a-b就等于a+(-b)，但不能出现负号，我们知道Java中整型数值编码方式为补码，所以一个数对应的负数就这个数“取反加1”，
- public static int sub(int a, int b){
- return add(a, add(~b, 1));
- }
1. Multiply a number by a power of two using bit left shift
a << b = a * 2^b2. Divide a number by a power of two using bit right shift
a >> b = a / 2^b3. Toggle a specified bit in a bit string without effecting other bits
bit_string = bit_string ^ (1 << positionOfBitToToggle)
4. Checking if a bit is on or off without affecting other bits
int isAvailable (int bitString, int targetNum)
{
return bit_string & (1 << targetNum);
}
http://codesam.blogspot.com/2011/01/bit-manipulation-tips-tricks-part-2.html1. Turning a bit off without affecting other bits
turnBitOff (int bitString, int bitPosition)
{
return bitString & ~(1 << bitPosition);
}
2. Turning a bit on without affecting other bitsturnBitOn (int bitString, int bitPosition)
{
return bitString || (1 << bitPosition);
}
http://www.1point3acres.com/bbs/thread-73742-1-1.html再准备面试的时候总结了一下关于bit manipulation可能用到的东西。在这里和大家分享一下～
x ^ 0s = x x & 0s = 0 x | 0s = x
x ^ 1s = ~x x & 1s = x x | 1s = 1s
x ^ x = 0 x & x = x x | x = x
boolean getBit(int i, int num){
return ( (num & (1 << i)) != 0 );
}
int setBit(int i, int num){
return num | (1 << i);
}
int clearBit(int num, int i) {
int mask = ~(1 << i);
return num & mask;
}
int clearBitMSBthroughI(int num, int i){
int mask = (1<< i) -1;
return num & mask;
}
int clearBitsIThrough0(int i, int num) {
int mask = ~( (1 << (i+1) ) -1 );
return num & mask;
}
int updateBit(int i, int num, int v){
int mask = ~(1 << i);
return (num & mask) | (v << i);
}
http://blog.csdn.net/earthma/article/details/46762943
值为1且最靠右的位元置为0 (如果存在): 0101 1110 => 010 1100 : x&(x-1)
值为0且最靠右的位元置为1 (如果存在): 0101 1110 => 010 1111 : x|(x+1)
将尾部的所有连续的1置为0(如果存在): 0101 0111 => 0101 0000 : x&(x+1)
将尾部的所有连续的0置为1(如果存在): 0101 1000 => 0101 1111 : x|(x-1)
将最靠右的0置为1(如果存在)，且其他位元置为0: 0101 0111 => 0000 1000 : ~x&(x+1)
将最靠右的1置为0(如果存在)，且其他位元置为1: 0101 1000 => 1111 0111 : ~x|(x-1)
将尾部的连续0置为1(如果存在)，且其他位元置为0: 0101 1000 => 0000 0111 : ~x&(x-1) or ~(x|-x) or (x&-x)-1
将尾部的连续1置为0(如果存在)，且其他位元置为1: 0101 0111 => 1111 1000 : ~x|(x+1)
保留最右的1(如果存在)，其他位元置为1: 0101 1000 => 0000 1000 :x&(-x)
最靠右的1及其右边的位元置为1，左边置为0: 0101 1010 => 0000 1111 : x^(x-1)
最靠右的0及其右边的位元置为1，左边置为0: 0101 1010 => 0000 0111 : x^(x+1)
右侧首个连续的1置为0: 0101 1100 => 0100 0000 (((x|(x-1))+1&x) or ((x&-x)+x)&x
进阶：
求比某个数大且位元1的个数相同的数 例如 xxx0 1111 0000 => xxx1 0000 0111
令 x = xxx0 1111 0000
s = x&-x
r = s+x
y = r | ( ( x ^ r ) << 2 / s)
两数的平均数：
(x&y) + ((x^y)>>1) 下取整
(x|y) - ((x^y)>>1) 上取整
统计位元‘1’的个数：
1.二分搜索法：
x = (x & 0x5555 5555) + ((x>>1) & 0x5555 5555)
x = (x & 0x3333 3333) + ((x>>2) & 0x3333 3333)
x = (x & 0x0F0F 0F0F) + ((x>>4) & 0x0F0F 0F0F)
x = (x & 0x00FF 00FF) + ((x>>8) & 0x00FF 00FF)
x = (x & 0x0000 FFFF) + ((x>>16) & 0x0000 FFFF)
例举一个八位数：
x = 1 0 1 1 1 1 0 0
x1 = 01 10 10 00
x2 = 0011 0010
x3 = 00000101 = 5
上述代码中有多余的与操作
可以写成如下简单代码：
int pop(unsigned x){
x = x - ((x>>1) & 0x5555 5555)
x = (x & 0x3333 3333) + ((x>>2) & 0x3333 3333)
x = (x+(x>>4)) & 0x0F0F 0F0F
x = x+(x>>8)
x = x + (x>>16)
return x& 0x0000 003F
}
第一行中x的值是由以下公式而来：
pop(x) = x - [x/2] - [x/4]-···-[x/2^31]
