目录

一、异或习题补充

1.260. 只出现一次的数字 III - 力扣（LeetCode）

二、位运算左移

1.概念

1）二进制形态

2）执行结果

3）负数左移的执行结果

4）左移负数位

5）左移溢出

2.应用

1）取模转换为位运算

2）生成标记码

a.标记位置1

b.标记位置0

c.标记位取反

3.习题

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

2）231. 2 的幂 - 力扣（LeetCode）

3)476. 数字的补数 - 力扣（LeetCode）

4)338. 比特位计数 - 力扣（LeetCode）

三、位运算右移

1.概念

1）二进制形态

2）执行结果

3）负数右移

4）右移负数位

2.应用

1）去掉低k位

2)取低位连续1

3）取第k位的值

3.习题

1.191. 位1的个数 - 力扣（LeetCode）

2.231. 2 的幂 - 力扣（LeetCode）​​​​​​

3.342. 4的幂 - 力扣（LeetCode）

4.405. 数字转换为十六进制数 - 力扣（LeetCode）

四、位运算按位取反

1.概念

2.应用

 1）0的取反

a)有符号整型

b)无符号整型

 2)相反数

3）代替减法

4)代替加法

3.题目

一、异或习题补充

1.260. 只出现一次的数字 III - 力扣（LeetCode）

class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
long long xornum=0;
for(int num:nums)
{
xornum^=num;
}
long long mask=xornum & (-xornum);//负数的二进制形式在电脑中以补码存在，补码=反码+1. 都是1时为1. 取最后一个二进制位为1的数字。
int a=0,b=0;
for(int num:nums)
{//把数组分为两组。
最后那两个数位或的最低位为1，肯定有一个数的二进制位是1，另一个是0.
if((num&mask)==0)
a^=num;
else
b^=num;
}
return {a,b};
}
};

2.861. 翻转矩阵后的得分 - 力扣（LeetCode）

3.1442. 形成两个异或相等数组的三元组数目 - 力扣（LeetCode）

二、位运算左移

1.概念

1）二进制形态

x<<y

表示将x左移y位，这里的位是二进制位。

在尾部添y个0

2）执行结果

x<<y的执行结果等价于：x * 

注意：常用当x=1时，1<<y表示 2的幂

3<<5
即3*2^5
96
011
01100000
1*2^5+1*2^6=96

3）负数左移的执行结果

- (x << y)  和 (-x) << y 等价

4）左移负数位

32<<-1 //16
32<<-5 //0
32<<-6 //0

左移负数位与右移对应正数数值位一致

5）左移溢出

溢出会回来。取余。

0b10000000000000000000000000000001;
//输出为-2147483647
左移1位。得到最高位的1被移除去，最低位补0。0b10
2

2.应用

1）取模转换为位运算

x%(pow(2,y))  可以转换为位与

x&((1<<y)-1)

2）生成标记码

a.标记位置1

x，对它二进制位的第k位置为1（从0开始，从低到高数）

• x|(1<<k)
• 位或运算。位或1，结果1；位或0，结果不变。

b.标记位置0

x，对它二进制位的第k位置为0（从0开始，从低到高数）

• x &(~(1<<k))
• 第k位为0，其他位为1， ~(1<<k)
• 位与运算：位与0，结果0；位与1，结果不变。

c.标记位取反

x，对它二进制位的第k位置为取反（从0开始，从低到高数）

• x^(1<<k)
• 异或运算：异或1，结果取反；异或0，结果不变

3.习题

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

class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t rev = 0;//与0异或为本身。
for (int i = 0; i < 32 && n > 0; ++i) {
rev ^= ((n & 1) << (31 - i));//n&1判断n的奇偶性，即看n的末位为0还是1
n >>= 1;
}
return rev;
}
};

2）231. 2 的幂 - 力扣（LeetCode）

class Solution {
public:
bool isPowerOfTwo(int n) {
if(n<=0)
return false;
if((n&(n-1))==0)
return true;
return false;
}
};

class Solution {
public:
bool isPowerOfTwo(int n) {
if(n<=0)
return false;
for(int i=0;i<32;i++)
{
if(1<<i==n)
return true;
}
return false;
}
};

3)476. 数字的补数 - 力扣（LeetCode）

class Solution {
public:
int findComplement(int num) {
//题干中整数与它的补数相加为n个1，n为整数的二进制位数。
long long ans=1;
while(ans<=num)
{
ans<<=1;//转换为二进制： num有几位，ans就有几个0，头是1
}
return ans-1-num;
}
};

4)338. 比特位计数 - 力扣（LeetCode）

class Solution {
public:
vector<int> countBits(int n) {
vector<int> ans(n+1);
for(int i=0;i<=n;i++)
{
int b=i;
while(b)//一定要舍一个中间量=i，不然i的值每次都会归于0
{
ans[i]+=b&1;
b>>=1;
}
}
return ans;
}
};

三、位运算右移

1.概念

1）二进制形态

• x>>y
• 将x右移y位；
• 对于正数，右移y位；对于负数，右移y位后，高位补1

2）执行结果

等价于   floor( )     floor是向下取整

0b1010111>>3
1010 即10

3）负数右移

- (x>>y)  等价于 (-x)>>y

4）右移负数位

右移尽量不用负数，会报错，但是运行结果正确。

2.应用

1）去掉低k位

x，去掉它的低k位，输出

x>>k

2)取低位连续1

获取x地位连续的1并且输出

(x^(x+1))>>1

    图源：英雄哪里出来

3）取第k位的值

获取一个数x的第k位的值并输出

(x>>k)&1

3.习题

1.191. 位1的个数 - 力扣（LeetCode）

class Solution {
public:
int hammingWeight(uint32_t n) {
int sum=0;
while(n)
{
n&=(n-1);
sum++;
}
return sum;
}
};

class Solution {
public:
int hammingWeight(uint32_t n) {
int sum=0;
while(n)
{
sum+=n&1;
n>>=1;
}
return sum;
}
};

2.231. 2 的幂 - 力扣（LeetCode）​​​​​​

bool isPowerOfTwo(int n){
int i;
if(n <= 0) {
return false;
}
while(1) {
if(n == 1) {
return true;
// 1在最高位。
}
if(n & 1) {
return false;
// 1出现在非最高位上
}
n >>= 1;
}
return false;
}

3.342. 4的幂 - 力扣（LeetCode）

class Solution {
public:
bool isPowerOfFour(int n) {
return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1;
}//n&(n-1)==0 证明n为偶数。 n%3==1
n是4的倍数。
};

4.405. 数字转换为十六进制数 - 力扣（LeetCode）

class Solution {
public:
string toHex(int num) {
if (num == 0)
return "0";
string ans = "0123456789abcdef";
// 0-15映射成字符
unsigned int n = num;
// 转为为非符号数,不让符号位参与计算
string res = "";
while (n > 0)
{
res += ans[n%16]; //n%16也可以写成n&15
n >>= 4;
//即 n/=16;
}
reverse(res.begin(),res.end());
return res;
}
};

四、位运算按位取反

1.概念

~x

取反是对32位二进制整数取反。

2.应用

 1）0的取反

• 答案：应该是32个1，  即-1，但是实际输出却是-1.
• 原因：C++和C语言中有两种类型的 int ，分别为unsigned int 和 signed int  ,int是signed int 的简称。

a)有符号整型

         signed int ，最高位表示符号位，所以只有31位能表示数值，能够表示的数值范围是：

                                                    

对于有符号整型，printf输出用%d

b)无符号整型

   unsigned int ，不需要符号位，所以32位能表示数值，能够表示的数值范围是：

                                                    

对于无符号整型，printf输出用%u

 2)相反数

 利用补码的定义，对于正数x，它的相反数的补码就是x二进制取反+1(补码=反码+1)，即 ~x+1

3）代替减法

不能用加号。x-y,可以理解成 x+(-y) 即，x+~y+1

4)代替加法

不能用减号。x+y,可以理解成   x-(-y)，即x-(~y+1)

3.题目

面试题 05.01. 插入 - 力扣（LeetCode）

class Solution {
public:
int insertBits(int N, int M, int i, int j) {
int k;
//先把N的i到j位清零
for(k=i;k<=j;k++)
{//举例：（1<<2）表示00000100，取反后得11111011，N&=（11111011）表示将N的第2位变为0（位数从0开始记）
N&=~(1<<k);
}
//位与0，结果0，位与1结果不变。
return N|(M<<i);//位或0，结果不变。
}
};

最后

以上就是任性手套为你收集整理的位运算左移、右移、按位取反一、异或习题补充二、位运算左移三、位运算右移四、位运算按位取反的全部内容，希望文章能够帮你解决位运算左移、右移、按位取反一、异或习题补充二、位运算左移三、位运算右移四、位运算按位取反所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。