常用的位操作 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：常用的位操作

评论礼仪 见这里，违者直接拉黑。

[Feyl]

有关位运算的知识涉及的都是计算机组成原理课程的内容与数值在计算机中存储的格式有关（原码、反码、补码、移码...等相关的内容），至于编程语言在底层如何表示和处理数值的还没有研究过。

下面均以8位格式表示各个整数，写一下个人对以上“奇淫技巧”的理解。

4. 判断两个数是否异号 在计算机中，带符号整数是以补码的形式存储。 二进制表示的首位为符号位，符号位为 0 时表示正数，符号位为 1 时表示负数。

int x = -1, y = 2; // -1的补码表示：1,1111111；2的补码表示：0,0000010 
bool f = ((x^y) < 0) // (-1)^2 补码表示：1,1111101   符号位为1表示负数（小于0）所以f为true
int x = 3, y = 2; // 3的补码表示：0,0000101；2的补码表示：0,0000010 
bool f = ((x^y) < 0) // (3)^2 补码表示：0,0000111   符号位为0表示正数（大于0）所以f为false

5. 不用临时变量交换两个数

int a = 1, b = 2; // a： 0,0000001   b：0,0000010
a ^= b; // a = a^b   a：0,0000011  将两个值二进制表示的相同的部分0,00000保持不变，不同的部分后两位均变为1 赋值给a 
b ^= a; /* ... a再次与b做异或位运算时  之前两个值二进制表示的相同的部分0,00000仍保持不变，
			剩下的位 与b不同的部分取值1，与b相同的部分取值0。则得到原来的a的二进制表示 0,0000001，
			此时相当于将原来的a的值赋值给了b  */
a ^= b;/*同理， a = a^b （b现在的二进制表示是原来的a的二进制表示 0,0000001，
		等号右边a的二进制表示是原来二者二进制表示位不相同的位取值为1时的值及0,0000011） 
		异或运算相当于把a的二进制表示变为原来b的二进制表示0,0000010（可以动手计算一下）。
		相当于将原来的b的值赋值给了a。*/
// 现在 a = 2, b = 1

6. 加一

int n = 1; //0,0000001
n = -~n; //先取反得到 1,1111110 再变为负数得到0,0000010
// 现在 n = 2

因为变为负数操作底层补码实现是 “将对应正数n的二进制位表示各个位取反后加一。” 那么两次操作（取反~和取负数-）相当于两次取反（及还原）后再加1，相当于原值+1。

7. 减一

int n = 2;
n = ~-n;
// 现在 n = 1

同6，但变化稍微不同。

可以再举一个数的例子看一下如何“减一”

例如： n = 4 0,0000100 -> 1,1111011 + 1 -> 1,1111100 （取负数）

​ - > 0,0000011 （再取反） //3

0,1010111 -> 1,0101000 + 1 -> 1,0101001

​ -> 0,1010110

不难看出规律：二进制位经过取反加1后，相当于二进制取反后从右至左的第一个为0的位的左边的位与原值的二进制位均相反，右边的位与原值的二进制位均相同。再次取反，左边的位还原，右边的位取反相当于 -1。

[hwhaocool]

【缺失的元素】，可以这样理解 因为异或满足交换律，所以 1^2^3 = 3^2^1 = 1^3^2，顺序无所谓的， 所以无论数组里数字是什么顺序，异或结果是一样的，所以可以写成 0^1^2^3...^n (注意这里面少一个数) （题目特意标明了 nums 中的所有数字都 独一无二） 索引的异或是 0^1^2^3...^n-1 (这里面的数字是完整的) 把数组里的数字异或结果和索引异或结果，再异或一下，就变成了：

(0^1^2^3...^n) ^ (0^1^2^3...^n-1)

因为边界不一样，n 消不掉，所以 还需要补一个 n (0^1^2^3...^n) ^ (0^1^2^3...^n-1) ^ n

这样算完之后

• 如果没有缺数字，结果就是0；
• 如果缺了一个数字，那么这个数字就消不掉，其它全部消了，所以结果就是这个数字

[Alwin4Zhang]

268【丢失的数字】

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        # 常规做法
        # for i, num in zip(range(len(nums) + 1), sorted(nums)):
        #     if i == num:
        #         continue
        #     return i
        # return len(nums)

        # 异或特性：数字异或自身为0，异或0为自身
        res = 0
        for num in nums:
            res ^= num
        for i in range(len(nums) + 1):
            res ^= i
        return res

[lihuagang03]

打卡，感谢楼主！

[LebronHarden1]

不用楼上这么去理解的,你把数字和下标都摆在一行,然后两个数值相等的一组抹成0,你就会发现最终就只会有那个丢失的数字的索引孤零零的留在原地,然后0异或它作为结果返回即可.

[cheng-miao]

daka

[HCWGH]

补充个bitmap和bit位数的操作

int bitNum = 0;

//给第i为赋值为1
bitNum |= 1 << i;

//第i位取反
bitNum ^= 1 << i;

//判断第i位是否为1
((bitNum >> i) & 1) == 1

    
    
 //bit数组
 long[] bitArray = new long[10];

//查询num在数组索引中的位置
 int index = num / 64;
 或
 int index = num >> 6;

//位于bit位中的索引
 int bitIndex = num % 64;

//第num位赋值为1
long[index] |= 1 << bitIndex;

//第num位取反
long[index] ^= 1 << bitIndex;

//判断第num位是否为1
((long[index] >> bitIndex) & 1) == 1;