leetcode刷题笔记——位运算

C/C++语言中逻辑右移和算数右移共享同一个运算符>>

如果运算数类型是unsigned则采用逻辑右移，而signed则采用算数右移。对于signed类型的数据，如果需要使用算数右移，或者unsigned类型的数据需要使用逻辑右移，都需要进行类型转换。

#include
using namespace std;
 
int main(){
    int a=0xFFFFFFFF;
    cout<<(unsigned)a>>1<
    cout<<(a>>1)<

常用位运算技巧：

1. n&1，n>>=1;

n>>=1 即 n=n>>1

2. n=n&(n-1)

n&(n-1)：把n的二进制中，最后一个出现的1改为0

3.异或

异或：同0异1

任何数和本身异或为0
应用举例：将nums中所有数字执行异或运算，留下的结果则为出现一次的数字x

即

4.进位：carry=(a&b)<<1

n & 1

n & 1：取 n 的二进制位最后一位的值

两个数 或 运算

二进制运算里或运算 等价于 没有进位的加法运算 举个例子 两个32位二进制数字 一个低16位全是0 另一个高16位全是0 他们相加不会产生进位 因此在这里，或运算 等价于 加法运算

常常用于将两个二进制数拼接起来：

n = (n >> 16) | (n << 16);
将 n 的高 16 位和低 16 位交换次序，然后拼接起来

 

妙蛙种子吃着妙脆角妙到了米奇妙妙屋，妙到家了 ：

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        n = (n >> 16) | (n << 16); //低16位与高16位交换
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8); //每16位中低8位和高8位交换; 1111是f
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4); //每8位中低4位和高4位交换;
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2); //每4位中低2位和高2位交换; 1100是c,0011是3
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1); //每2位中低1位和高1位交换; 1010是a,0101是5
        return n;
    }
};

相关题目

190. 颠倒二进制位 - 力扣（LeetCode）