由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 今天突然想写这个:位运算题目总结
相关主题
reverse bits problem算法--一个MXN matrix (0's and 1's)内求最大 rectangle(1's)
一道位运算题two questions
被基础题搞挂了请教一道careercup 150上的题
divide two integers问一个老数组题
矩阵变换题新鲜的L一面
A家一道题大意了,尼玛
文学城一道题,你做出来了吗?M面经
刚才的amazon phone interview 第一轮YHOO phone interview
相关话题的讨论汇总
话题: int话题: 交换话题: rlt话题: return话题: xor
进入JobHunting版参与讨论
1 (共1页)
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
2
Thanks
l****c
发帖数: 782
3
不错啊。有时间拜读下!
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
7
Mark收藏 补充一下,用×和-可能会溢出
d***k
发帖数: 3225
8
mark这个
太有用了
T********e
发帖数: 63
9
mark
j********l
发帖数: 325
10
m
1 (共1页)
进入JobHunting版参与讨论
相关主题
YHOO phone interview矩阵变换题
facebook on site后多久给消息啊A家一道题
Divide Two Integers文学城一道题,你做出来了吗?
问一道 Interviewstreet 上的题 (JAVA)刚才的amazon phone interview 第一轮
reverse bits problem算法--一个MXN matrix (0's and 1's)内求最大 rectangle(1's)
一道位运算题two questions
被基础题搞挂了请教一道careercup 150上的题
divide two integers问一个老数组题
相关话题的讨论汇总
话题: int话题: 交换话题: rlt话题: return话题: xor