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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果没有准备过,估计很多人面试遇到位运算的题目都会头疼,包括我自己,所以在此 : 总结一下位运算相关题目吧,从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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果没有准备过,估计很多人面试遇到位运算的题目都会头疼,包括我自己,所以在此 : 总结一下位运算相关题目吧,从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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 小小的补充一下 : : 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 | |
|