LeetCode编程训练 - 位运算(bit manipulation)

位运算基础说到与(&)、或(|)、非(~)、异或(^)、位移等位运算,就得说到位运算的各种奇淫巧技,下面分运算符说明。1.与(&)计算式a&b,a、b各位中同为1才为1,否则为0,a&1和a%2效果一样;来看两道典型的题目,第1道计算整数二进制中1的位数://191.Numberof1BitsinthammingWeight(uint32_tn){intres=0;...

位运算基础

说到与(&)、或(|)、非(~)、异或(^)、位移等位运算,就得说到位运算的各种奇淫巧技,下面分运算符说明。

1. 与(&)

计算式 a&b,a、b各位中同为 1 才为 1,否则为0,a&1和a%2效果一样;来看两道典型的题目,第1道计算整数二进制中 1 的位数:

 //191. Number of 1 Bits int hammingWeight(uint32_t n) {  int res=0;  while(n!=0){n=n&(n-1);  res;  }  return res; }

n=n&(n-1)代表去掉整数n二进制中最左侧为 1 的位,例如n=12,则:

n -> 1 1 0 0&n-1  -> 1 0 1 1------------------  1 0 0 0

第2道判断一个数是否为4的乘方数(不能用loop解):

 //342. Power of Four bool isPowerOfFour(int num) {  if(num==INT_MIN) return false;  return !(num&(num-1)) && (num&0x55555555); }

以上0x55555555的二进制表示为……01010101 (偶数位为0、奇数位为1),像这样tricky的数还有:

0xaaaaaaaa : 10101010101010101010101010101010 (偶数位为1,奇数位为0)0x33333333 : 00110011001100110011001100110011 (1和0每隔两位交替出现)0xcccccccc : 11001100110011001100110011001100 (0和1每隔两位交替出现)0x0f0f0f0f : 00001111000011110000111100001111 (1和0每隔四位交替出现)0xf0f0f0f0 : 11110000111100001111000011110000 (0和1每隔四位交替出现)

相关LeetCode题:

191.Number of 1 Bits 题解

342.Power of Four 题解

201.Bitwise AND of Numbers Range 题解

2. 或(|)

计算式a|b,a、b各位中有一个为1则结果为1;来看一道题:有正整数n,求小于或等于n的2的最大乘方数(不能用loop解):

int largest_power(ing N) { N = N | (N>>1); N = N | (N>>2); N = N | (N>>4); N = N | (N>>8); N = N | (N>>16); return (N 1)>>1;}

看起来是不是相当tricky,其思路是用或运算将右边位数置为1,例如n=01010,通过或操作n变为01111,则n 1为10000,所求为01000;更详细解释见 这里

相关LeetCode题:

190.Reverse Bits 题解

898.Bitwise ORs of Subarrays 题解

3. 异或(^)

计算式a^b,a、b对应位相同为0,相异则为1;根据异或性质有a^a=0,a^0=a,利用该性质可解决136. Single Number:

 //136. Single Number int singleNumber(vector<int>& nums) {  int res=0;  for(auto x:nums) res^=x;  return res; }

相关LeetCode题:

136.Single Number题解

461.Hamming Distance 题解

371.Sum of Two Integers 题解

260.Single Number III 题解

4. 位移

a<<1效果相当于a*2(不超出数值类型范围情况下),a>>1效果相当于a/2,位移常用于按位轮询。

相关LeetCode题:

405.Convert a Number to Hexadecimal 题解

751.IP to CIDR 题解
逐位计算结果

有意思的时当我们的目光放到bit的维度,一些问题可以按位来求解,例如169. Majority Element求数组中出现次数大于一半的数:

 //169. Majority Element int majorityElement(vector<int>& nums) {  int mask=1,size=nums.size(),ret=0;  for(int i=0;i<32;i  ){int count=0;for(int j=0;j<size;j  ){ if(nums[j]&mask) count  ; if(count>size/2){  ret|=mask; //逐位计算结果break; }}mask<<=1;  }  return ret; }

相关LeetCode题:

169.Majority Element 题解

477.Total Hamming Distance 题解

421.Maximum XOR of Two Numbers in an Array题解

使用bit表示数据

在一些场景下我们希望用bit来表示数据,或节省空间或利用bit的运算特性来表示状态转换。

相关LeetCode题:

187.Repeated DNA Sequences 题解

289.Game of Life题解

源文地址:https://www.guoxiongfei.cn/cntech/14877.html