位运算总结_牛客博客

常用的位运算有6个：
&
|
~
^ 相当于不进位的加法
<< << 1 相当于x2 上取整 << 3相当于x8
>> >> 1 相当于/2 下取整

技巧篇

lowbit运算1：n & -n 表示 n的二进制表示里最右边的1，所以 n & -n == n 表示n为2的整数次幂，n & -n < n则n不为2的整数次方
lowbit运算2：n & (n -1）就会把该整数二进制的最后一位1置零
异或运算^: a ^ a = 0 , 0 ^ a = a而且异或满足交换律和结合律

实战篇：剑指offer15题——二进制中的1的个数

本题思考方式可以将数字的最后一位和1进行与运算，然后右移来统计二进制中的1.但是如果整数为负数的时候，就会出现补1的情况从而造成死循环。

解决办法1

将输入的数字强制转换成unsigned int类型即可。

class Solution {
public:
    int NumberOf1(int n) {
        int res = 0;
        unsigned int un = n; 
        while (un) res += un & 1, un >>= 1;
        return res;
    }
};

解决办法2

设置一个unsigned int flag = 1 每次与输入整数进行与运算后判断是否为1尔后左移统计1的个数，从而负数高位补零造成死循环。

class Solution {
public:
    int NumberOf1(int n) {
        int res = 0;
        unsigned int flag = 1; 
        while (flag) {
        	if (flag  & n) res++;
        	flag <<= 1;
        }
        return res;
    }
};

解决办法3

n & (n -1）就会把该整数二进制的最后一位1置零。那么二进制数有多少个1就会进行多少次这样的操作。

class Solution {
public:
    int NumberOf1(int n) {
        int res = 0;
        while (n){
        	n &= (n + 1);
        	res++;
        }
        return res;
    }
};

LeetCode231:2的幂

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
利用lowbit运算即可判断：

class Solution {
public:
    bool isPowerOfTwo(int n) {
        //return n > 0 && (n & -n) == n;
        return (n > 0) ? ((n & -n) == n) : false;
    }
};

LeetCode762:二进制表示中质数个计算置位

给定两个整数 L 和 R ，找到闭区间 [L, R] 范围内，计算置位位数为质数的整数个数。
注意：

计算置位代表二进制表示中1的个数。
L, R 是 L <= R 且在 [1, $10^6 </annotation> </semantics> </math>$
R - L 的最大值为 10000。

解题思路

根据R的上限可以判断R <= $2^{20} </annotation> </semantics> </math>$
在循环前设置结果变量res,初始化为0；
外循环遍历数据范围，内循环遍历当前数据二进制的每一位进行lowbit操作，将数据最右侧1置零，同时统计1的个数。若统计个数在枚举的容器中，则结果加1；最后返回res就是最终答案。

class Solution {
public:
    int countPrimeSetBits(int L, int R) {
        unordered_set<int> prime({2, 3,5,7,11,13,17,19});
        int res = 0;
        for (int n = L; n <= R; n++){
        	int sum = 0;
        	for (int k = n; k; k &= (k - 1))
        		sum++;
        	if (prime.count(sum))
        		res++;
        }
        return res;
    }
};

LeetCode136:只出现1次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
运用异或的性质即可，相同数字异或相当于消消乐，即为0，而0与任何数字异或都等于当前数字。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
    	int res = 0;
    	for (auto x : nums)
    		res ^= x;
    	return res;
    }
};

LeetCode137:只出现1次的数字II

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
要求：不使用额外的空间

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int bit = 0; bit < 32; bit++){
            int counter = 0;
            for (int i = 0; i < nums.size(); i++)
                counter += (nums[i] >> bit) & 1;
            res += (counter % 3) << bit;
        }
        return res;
    }
};

LeetCode137:只出现1次的数字III

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int s = 0;
        for (auto x : nums) s ^= x; // 消除了相同数字，只剩下只出现一次的两个数字异或
        //假设 s = a ^ b
        
        int k =  0;
        while (!(s >> k & 1)) // 求一个整数s的第k位是0还是1，比较常用的技巧
            k++;
        
        int s2 = 0;
        for (auto x : nums)
            if (x >> k &1)
                s2 ^= x;  // s2 = a
        // 所以 s ^ s2 = a ^ b ^ a = b;
        return vector<int>({s2, s ^ s2});
        
    }
};

LeetCode476: 数字的补数

给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。

输入两个数m和n，计算需要改变m的二进制表示的多少位才能得到n。