本文主要是介绍位操作符的总结 Brian Kernighan算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 1 Brian Kernighan 算法
- 1.1
- 2 判断一个数字n的比特位中1的个数
- 2 leetcode231. 2的幂
- 3 201. 数字范围按位与
- 4 不创建临时变量,交换两个数字
1 Brian Kernighan 算法
这个算法的意思是,对任何一个数 n n n, n & ( n − 1 ) n\&(n-1) n&(n−1)的结果是 n n n的比特位最右端的1变为0的结果。例如, n = 12 , n − 1 = 11 , 11 & 12 = 8 n=12,n-1=11,11\&12=8 n=12,n−1=11,11&12=8
1.1
n & (~n + 1)提取出整数n最后一位为1的数
举例:n = 01101,~n 是将n按位取反就是10010,~n + 1 = 10011,最后,n & (~n + 1) = 00001
2 判断一个数字n的比特位中1的个数
直观的,我们可以对n右移以为然后与1相与,循环32次即可,但如果我们使用Brian Kernighan 算法,会变得简单许多,循环的次数仅与n中1的个数有关。两种快速方法:
int fun1(int num)
{int count = 0;while (num){num -= num & (~num + 1);++count;}return count;
}
int fun2(int num)
{int count = 0;while (num){num = num & (num - 1);++count;}return count;
}
int main()
{int a = 16516;bitset<10> b(a);cout << b << endl;cout << fun1(a) << endl;cout << fun2(a) << endl;
}
2 leetcode231. 2的幂
给定一个整数,编写一个函数来判断它是否是 2 的幂次方。
首先,我们直到2的次方数都是只有一个1的,
1 − > 1 , 2 − > 10 , 4 − > 100 , 8 − > 1000 , 16 − > 10000.... 1->1,2->10,4->100,8->1000,16->10000 .... 1−>1,2−>10,4−>100,8−>1000,16−>10000....
也是,直观的,我们也可以暴力循环32次,找出数字1的个数,随后判断。但我们也可以通过Brian Kernighan 算法,一步进行解决。试想以下,如果有 8 − > 1000 8->1000 8−>1000,那么 7 − > 0111 7->0111 7−>0111,发现 8 & 7 = 0 8\&7=0 8&7=0,推广的所有的2的次方数,也是一个结果。
bool isPowerOfTwo(int n){if(n==0)return false;return n&(n-1)==0;
}
3 201. 数字范围按位与
给定范围 [m, n],其中 0 <= m <= n <= 2147483647,返回此范围内所有数字的按位与(包含 m, n 两端点)。
思路:首先,m=26,n=30,我们将这个范围的数字用二进制表示
11010, 11011 , 11100 , 11101 , 11110
输出的结果24 ->11000
可以发现,只要找到二进制的左边的公共部分,即可。
同样采用Brian Kernighan 算法,我们只需将较大端不断缩小,也就是将较大端的最左边的二进制位的1变为0,直到较小端大于较大端。
/*
m=5 101
n=7 111
n->6->4 在return 4&5=4
*/int rangeBitwiseAnd(int m, int n) {while (m < n) {n = n & (n - 1);}return n;}
4 不创建临时变量,交换两个数字
第一种方法 A = A + B B = A − B = ( A + B ) − B = A A = A − B = A + B − A = B A = A+B\\ B = A-B=(A+B)-B=A\\ A = A-B=A+B-A=B A=A+BB=A−B=(A+B)−B=AA=A−B=A+B−A=B
完成交换。
vector<int> swapNumbers(vector<int>& numbers) {numbers[0] = numbers[0]+numbers[1];numbers[1] = numbers[0]-numbers[1];numbers[0] ^= numbers[0]-numbers[1];return numbers;}
第一种方法可能会溢出,所以可以使用按位异或运算符。
vector<int> swapNumbers(vector<int>& numbers) {numbers[0] ^= numbers[1];numbers[1] ^= numbers[0];numbers[0] ^= numbers[1];return numbers;}
这篇关于位操作符的总结 Brian Kernighan算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!