目录
一、异或习题补充
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.题目
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）
x<<y
表示将x左移y位，这里的位是二进制位。
在尾部添y个0
x<<y的执行结果等价于：x *
注意：常用当x=1时，1<<y表示 2的幂
3<<5 即3*2^5 96
011 01100000 1*2^5+1*2^6=96- (x << y) 和 (-x) << y 等价
32<<-1 //16
32<<-5 //0
32<<-6 //0左移负数位与右移对应正数数值位一致
溢出会回来。
取余。
0b10000000000000000000000000000001;
//输出为-2147483647
左移1位。得到最高位的1被移除去，最低位补0。0b10 2
x%(pow(2,y)) 可以转换为位与
x&((1<<y)-1)
x，对它二进制位的第k位置为1（从0开始，从低到高数）
x，对它二进制位的第k位置为0（从0开始，从低到高数）
x，对它二进制位的第k位置为取反（从0开始，从低到高数）
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;
}
};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;
}
};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;
}
};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;
}
};
- x>>y
- 将x右移y位；
- 对于正数，右移y位；对于负数，右移y位后，高位补1
等价于 floor(
) floor是向下取整
0b1010111>>3
1010 即10- (x>>y) 等价于 (-x)>>y
右移尽量不用负数，会报错，但是运行结果正确。
x，去掉它的低k位，输出
x>>k获取x地位连续的1并且输出
(x^(x+1))>>1
图源：英雄哪里出来
获取一个数x的第k位的值并输出
(x>>k)&1class 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;
}
};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;
}
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的倍数。
};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;
}
};
~x
| 操作数 | 取反结果 |
| 1 | 0 |
| 0 | 1 |
取反是对32位二进制整数取反。
- 答案：应该是32个1， 即
- 原因：C++和C语言中有两种类型的 int ，分别为unsigned int 和 signed int ,int是signed int 的简称。
signed int ，最高位表示符号位，所以只有31位能表示数值，能够表示的数值范围是：
对于有符号整型，printf输出用%d
unsigned int ，不需要符号位，所以32位能表示数值，能够表示的数值范围是：
对于无符号整型，printf输出用%u
利用补码的定义，对于正数x，它的相反数的补码就是x二进制取反+1(补码=反码+1)，即 ~x+1
不能用加号。x-y,可以理解成 x+(-y) 即，x+~y+1
不能用减号。x+y,可以理解成 x-(-y)，即x-(~y+1)
面试题 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，结果不变。
}
};