o****o
发帖数: 1398 | 1 如果没有准备过，估计很多人面试遇到位运算的题目都会头疼，包括我自己，所以在此
总结一下位运算相关题目吧，从leetcode,careercup还有本版学到的，留个纪念：
1. Toggle 5th-8th bit of a 32bit Integer 这是我自己编的题，不过对于理解XOR操
作有帮助
Ans: a = a ^ 0x000000F0;
2. 交换第i与第j位
这个思路是直接：抠出第i位和第j位，交换之后再置位，可是实现比较麻烦啊，分情况
考虑比较好：
（1）如果第i位和第j位相同，不用换
（2）如果不同，用题1的方法，来个掩码，仅toggle第i位和第j位
Ans:
//Assume i,j start from 0
int exchange(int a, int i, int j) {
if( ((a>>i)&1) != ((a>>j)&1) ) {
a = a ^ ((1<
}
return a;
}
3. Turn off the rightmost 1-bit
Ans: x = x & (x-1)
看个例子吧：
01011000 (x)
& 01010111 (x-1)
--------
01010000
延伸一下，如果 x & (x-1) == 0，那么x是什么数？所有bit位只有一个1，例如
01000000，也就是说x是2的整数倍2^n
4. 交换相邻的两个bit的值，例如 10101111 -> 01011111
思路：利用移位和掩码
int switch2(int x) {
int a = (x>>1)&(0x55555555); //右移1位，掩掉第1,3,5...位（从左向右数，起
始位按1开始）
int b = (x<<1)&(0xAAAAAAAA); //左移1位，掩掉第2,4,6...位（从左向右数，起
始位按1开始）
return a|b;
}
5. 反转一个32bit数的二进制位
方法1，利用题2的方法，交换第0位和最后一位(31th)，交换第1位和倒数第二位(30th)
int inverse(int x) {
for(int i=0; i<16; i++)
x = exchange(x, i, 31-i);
return x;
}
方法2，连续做以下操作：
交换相邻两位 （见题4）
交换相邻四位
交换相邻八位
交换相邻16位
int reverse(int x) {
x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);
x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2);
x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4);
x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8);
x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16);
return x;
}
凭感觉想想为什么吧:)
6. 位运算实现加法
开始思路是用循环一位一位做，并考虑进位。其实如果知道XOR(^)和AND(&)运算的特点
，直接批量操作：
XOR(^) 实现无进位加法，也就是说把两个数加起来，进位扔掉不管就是了。
AND(&) 其结果是进位，只不过需要左移1位，想想1 & 1结果是1，这个1可以看做是进
位，只不过需要进上去（<<1）
So, 两个数a和b相加:
x = a ^ b;
y = (a & b) << 1;
转换成了x和y相加，可是还是需要相加x和y呀？
答案是再接着用同样的方法转换！
那转换多少次啊？
递归！停止条件就是没有进位为止。
I see ...
int add(int a, int b) {
if(b == 0) return a;
return add( a^b, (a&b)<<1);
}
再仔细观察，这是个尾递归（惭愧，还是学习Scala语言知道这个概念的），可以不用
递归：
int add(int a, int b) {
while(b != 0) {
int x = a^b;
int y = (a&b)<<1;
a = x;
b = y;
}
return a;
}
7. 写个函数不用任何比较运算符，返回两个数中最大的
如何知道哪个大哪个小呢？ 例如a,b两个数，我们知道，
如果a>b, a-b返回正数，
如果a
利用最高位，看来有希望了，如果把最高位拿出来，那么就有：
a>b -> 0
a 1
事先定义一个数组：
rlt[0] = a;
rlt[1] = b;
于是就有了下面代码：
int max2(int a, int b) {
int rlt[] = {a, b};
int c = a - b;
return rlt[(c>>31)&1]; //或者(Java) rlt[c>>>31];
}
另外，也可以用
int c = (a-b)>>>31;
return a - c*(a - b); //算一下就知道了:)
8. 不用临时变量交换两个数a和b
这个题，貌似不可能啊，没想到还真能实现
方法1：为了便于解释，令：x=a; y=b;
x = x^y;
y = x^y; //这个相当于： (a^b)^b = a^(b^b) = a ^ 0 = a (异或XOR是可交换的)
x = x^y; //这个相当于： (a^b)^a = (a^a)^b = 0 ^ b = b
方法2：
x = x + y;
y = x - y; // (a+b) - b = a //这时候x=a+b, y=b
x = x - y; // (a+b) - a = b //这时候x=a+b, y=a
方法3：减也可以的！
x = x - y;
y = x + y;
x = y - x;
9. Divide a number by 3 without using *, /, +, -, % operators
有人贴过了
http://www.mitbbs.com/article_t/JobHunting/32182279.html
貌似用这个公式：
1/3 = 1/4 + 1/16 + 1/64 + ...
这是等比数列， let q=1/4, sum = q/(1-q) = 1/3
如果扩展一下，Divide a number by 7 without using *, /, +, -, % operators
貌似可以：1/7 = 1/8 + 1/64 + 1/(8*8*8) + ...
这也是等比数列， let q=1/8, sum = q/(1-q) = 1/7
不过这个解释也很好：
n = 4a + b （实际上：a=n/4（整除）, b=n%4）
n/3 = (4a+b)/3 = a + (a+b)/3, 所以剩下的问题就是递归解决(a+b)/3了，同理，这
是个尾递归，代码就不写了。 | c******n
发帖数: 710 | | l****c
发帖数: 782 | | i*******e
发帖数: 240 | 4 Thanks mark
★ 发自iPhone App: ChineseWeb 7.3
【在 o****o 的大作中提到】
: 如果没有准备过，估计很多人面试遇到位运算的题目都会头疼，包括我自己，所以在此
: 总结一下位运算相关题目吧，从leetcode,careercup还有本版学到的，留个纪念：
: 1. Toggle 5th-8th bit of a 32bit Integer 这是我自己编的题，不过对于理解XOR操
: 作有帮助
: Ans: a = a ^ 0x000000F0;
: 2. 交换第i与第j位
: 这个思路是直接：抠出第i位和第j位，交换之后再置位，可是实现比较麻烦啊，分情况
: 考虑比较好：
: （1）如果第i位和第j位相同，不用换
: （2）如果不同，用题1的方法，来个掩码，仅toggle第i位和第j位
| Z*****Z
发帖数: 723 | 5 小小的补充一下
x == 0的时候也成立~~~~~~~~~~~~~~~~~~
3.1 Fetch the right most 1-bit
Ans: x & -x
30th)
【在 o****o 的大作中提到】
: 如果没有准备过，估计很多人面试遇到位运算的题目都会头疼，包括我自己，所以在此
: 总结一下位运算相关题目吧，从leetcode,careercup还有本版学到的，留个纪念：
: 1. Toggle 5th-8th bit of a 32bit Integer 这是我自己编的题，不过对于理解XOR操
: 作有帮助
: Ans: a = a ^ 0x000000F0;
: 2. 交换第i与第j位
: 这个思路是直接：抠出第i位和第j位，交换之后再置位，可是实现比较麻烦啊，分情况
: 考虑比较好：
: （1）如果第i位和第j位相同，不用换
: （2）如果不同，用题1的方法，来个掩码，仅toggle第i位和第j位
| o****o
发帖数: 1398 | 6 赞
【在 Z*****Z 的大作中提到】
: 小小的补充一下
:
: x == 0的时候也成立~~~~~~~~~~~~~~~~~~
:
: 3.1 Fetch the right most 1-bit
: Ans: x & -x
: 30th)
| N****p
发帖数: 1691 | | d***k
发帖数: 3225 | | T********e
发帖数: 63 | | j********l
发帖数: 325 | |
|
