利用位运算可以解决的一些问题

位运算

这些位运算中我们可以特别注意一下异或操作，因为疑惑操作有以下三个性质：

1.任何数和0做异或运算，结果仍然时原来的数，即：a⊕0=a。

2.任何数和其自身做异或运算，结果是0，即：a⊕a=0;

3.异或运算满足交换律和结合率，即:a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。

利用这些性质，我们可以解决例如“只出现一次的数字”这样的问题：

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number

int singleNumber(int* nums, int numsSize){
    int ans=0;
    for(int i=0;i<numsSize;i++)
    ans^=nums[i];
    return ans;
}

对于左移操作来说，若左移时舍弃的高位不包含1，则每左移一位，相当于该数乘以2。同理，右移操作，每右移一位，相当于该数除以2。

另外还有一些位操作(https://labuladong.gitbook.io/algo/suan-fa-si-wei-xi-lie/chang-yong-de-wei-cao-zuo)：

利用或操作 | 和空格将英文字符转换为小写:

(‘a‘ | ‘ ‘) = ‘a‘

(‘A‘ | ‘ ‘) = ‘a‘

利用与操作 & 和下划线将英文字符转换为大写:

(‘b‘ & ‘_‘) = ‘B‘

(‘B‘ & ‘_‘) = ‘B‘

利用异或操作 ^ 和空格进行英文字符大小写互换:

(‘d‘ ^ ‘ ‘) = ‘D‘

(‘D‘ ^ ‘ ‘) = ‘d‘

判断两个数是否异号:

int x = -1, y = 2;
bool f = ((x ^ y) < 0); // true

int x = 3, y = 2;
bool f = ((x ^ y) < 0); // false

另外一个常用的算法操作：n&(n-1)。它的作用是消除数字n的二进制中的最后一个1。

从上面这个还可以引申出来的问题：

1.计算一个无符号整数的二进制表达式数字位数为1的个数（汉明重量）。

int hammingWeight(int n)
{
     int res=0;
     while(n!=0)
      {
        n=n&(n-1);
         res++;
       }    
    return res;
}        

2.判断一个数是否是2的指数

一个数如果是2的指数，那么它的二进制表示一定只含一个1

bool isPowerOfTwo(int n) {
    if (n <= 0) return false;
    return (n & (n - 1)) == 0;
}

利用位运算可以解决的一些问题

原文：https://www.cnblogs.com/happy2333/p/12989609.html