运算 | 彩潭有鲤的札记

type

status

date

slug

summary

位运算的应用

判断整数奇偶

一个整数，只要是偶数，对应二进制数的末尾一定为；只要是奇数，对应二进制数的末尾一定为。所以，通过与进行按位与运算，即可判断某个数是奇数还是偶数。

(x & 1) == 0 为偶数

(x & 1) == 1 为奇数

二进制数选取指定位

如果想要从一个二进制数中取出某几位，使取出位置上的二进位保留原值，其余位置为，可以使用另一个二进制数，使该二进制数上对应取出位置为，其余位置为。然后令两个数进行按位与运算（X & Y），即可得到想要的数。

比如要取二进制数的末尾位，则只需将与进行按位与运算，即01101010 & 00001111 == 00001010。

将指定位设置为1

如果想要把一个二进制数中的某几位设置为，其余位置保留原值，则可以使用另一个二进制数，使得该二进制上对应选取位置为，其余位置为。然后令两个数进行按位或运算（X | Y），即可得到想要的数。

比如想要将二进制数的末尾位设置为，其余位置保留原值，则只需将与进行按位或运算，即 01101010|00001111 = 01101111。

反转指定位

如果想要把一个二进制数的某几位进行反转，则可以使用另一个二进制数，使得该二进制上对应选取位置为，其余位置为。然后令两个数进行按位异或运算（X ^ Y），即可得到想要的数。

比如想要将二进制数的末尾位进行反转，则只需将与进行按位异或运算，即 01101010 ^ 00001111 = 01100101。

交换两个数

通过按位异或运算可以实现交换两个数的目的（只能用于交换两个整数）。

将二进制最右侧为1的二进位改为0

如果想要将一个二进制数最右侧为的二进制位改为，则只需通过 X & (X - 1) 的操作即可完成。

比如，，则 X & (X - 1) == 01101100 & 01101011 == 01101000

计算二进制中二进位为1的个数

通过 X & (X - 1) 可以将二进制最右侧为的二进制位改为，那么如果不断通过 X & (X - 1) 操作，最终将二进制变为，并统计执行次数，则可以得到二进制中二进位为的个数。

判断某数是否为2的幂次方

通过判断 X & (X - 1) == 0 是否成立，即可判断是否为的幂次方。

这是因为：

凡是的幂次方，其二进制数的某一高位为，并且仅此高位为，其余位都为。比如：、

不是的幂次方，其二进制数存在多个值为的位。比如：、

接下来使用 X & (X - 1) 操作，将原数对应二进制数最右侧为的二进位改为之后，得到新值：

如果原数是的幂次方，则通过 X & (X - 1) 操作之后，新值所有位都为，值为。

如果该数不是的幂次方，则通过 X & (X - 1) 操作之后，新值仍存在不为的位，值肯定不为。

位运算的常用操作

功能	位运算	示例
去掉最后一位	`x >> 1`	`101101 -> 10110`
在最后加一个 `0`	`x << 1`	`101101 -> 1011010`
在最后加一个 `1`	`(x << 1) + 1`	`101101 -> 1011011`
把最后一位变成 `1`	`x \| 1`	`101100 -> 101101`
把最后一位变成 `0`	`x \| 1 - 1`	`101101 -> 101100`
最后一位取反	`x ^ 1`	`101101 -> 101100`
把右数第 `k` 位变成 `1`	`x \| (1 << (k - 1))`	`101001 -> 101101, k = 3`
把右数第 `k` 位变成 `0`	`x & ~(1 << (k - 1))`	`101101 -> 101001, k = 3`
右数第 `k` 位取反	`x ^ (1 << (k - 1))`	`101001 -> 101101, k = 3`
取末尾 `3` 位	`x & 7`	`1101101 -> 101`
取末尾 `k` 位	`x & 15`	`1101101 -> 1101, k = 4`
取右数第 `k` 位	`x >> (k - 1) & 1`	`1101101 -> 1, k = 4`
把末尾 `k` 位变成 `1`	`x \| (1 << k - 1)`	`101001 -> 101111, k = 4`
末尾 `k` 位取反	`x ^ (1 << k - 1)`	`101001 -> 100110, k = 4`
把右边连续的 `1` 变成 `0`	`x & (x + 1)`	`100101111 -> 100100000`
把右边起第一个 `0` 变成 `1`	`x \| (x + 1)`	`100101111 -> 100111111`
把右边连续的 `0` 变成 `1`	`x \| (x - 1)`	`11011000 -> 11011111`
只保留右边连续的 `1`	`(x ^ (x + 1)) >> 1`	`100101111 -> 1111`
去掉右边起第一个 `1` 的左边	`x & (x ^ (x - 1))` 或 `x & (-x)`	`100101000 -> 1000`
从右边开始，把最后一个 `1` 改写成 `0`	`x & (x - 1)`	`100101000 -> 100100000`

位运算的题目

位1的个数

题目：编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。

示例：

运算，其运算结果恰为把的二进制位中的最低位的1变为0之后的结果：

比特位计数

题目：给一个整数n，对于0 <= i <= n中的每个i ，计算其二进制表示中1的个数 ，返回一个长度为n + 1的数组ans作为答案。

示例：

对于一个整数n，n&(n-1)可以将n的二进制最右边值为1的bit位置为0。

n的二进制比n&(n-1)的二进制中的1多1个，这样就可以得到状态转移公式：dp[n] = dp[n&(n-1)] + 1

丢失的数字

题目：给定一个包含[0, n]中n个数的数组nums ，找出[0, n]这个范围内没有出现在数组中的那个数。

示例：

对于二进制相同值的bit位进行异或运算值是0，比如1 ^ 1 = 0，0 ^ 0 = 0

针对区间[0,n]和数组nums中所有的元素做异或运算，nums中的元素会出现两次，没有出现在nums中的元素只会出现一次，两个相同的元素做异或值为0，最后的结果就是没有出现在nums中的元素。

假设，。0 ^ 1 ^ 2 ^ 3 ^ 3 ^ 0 ^ 1 = (0 ^ 0) ^ (1 ^ 1) ^ (3 ^ 3) ^ 2 = 0 ^ 2 = 2。最终2就是没有出现在nums中的数字。

两整数之和

题目：给你两个整数 a 和 b ，不使用运算符 + 和 - ，计算并返回两整数之和

二进制每一位相加，1+1对应的位会变成0，1+0对应的位是1，0+0对应的位是0，这可以通过异或（^）运算符来实现。

只有1+1会存在进位，这个可以通过与（&）运算符来实现。

颠倒二进制位

题目：颠倒给定的 32 位无符号整数的二进制位

示例：

运算符	描述	规则
`&`	按位与运算符	只有对应的两个二进位都为时，结果位才为
`\|`	按位或运算符	只要对应的两个二进位有一个为时，结果位就为
`^`	按位异或运算符	对应的两个二进位相异时，结果位为，二进位相同时则结果位为
`~`	取反运算符	对二进制数的每个二进位取反，使数字变为，变为
`<<`	左移运算符	将二进制数的各个二进位全部左移若干位。`<<`右侧数字指定了移动位数，高位丢弃，低位补
`>>`	右移运算符	对二进制数的各个二进位全部右移若干位。`>>`右侧数字指定了移动位数，低位丢弃，高位补