Bit Manipulation Tricks

Posted on | In , |

Summary

操作符 功能 用法
~ 位求反 ~var
<< 左移(乘法) var << position

右移(除法)    var >> position

& 位与 var1 & var2
^ 位异或 var1 ^ var2
| 位或 var1 | var2

NOT ( ~ ): Bitwise NOT is an unary operator that flips the bits of the number i.e., if the ith bit is 0, it will change it to 1 and vice versa. Bitwise NOT is nothing but simply the one’s complement of a number. Lets take an example.
N = 5 = (101)2
~N = ~5 = ~(101)2 = (010)2 = 2

AND ( & ): Bitwise AND is a binary operator that operates on two equal-length bit patterns. If both bits in the compared position of the bit patterns are 1, the bit in the resulting bit pattern is 1, otherwise 0.
A = 5 = (101)2 , B = 3 = (011)2 A & B = (101)2 & (011)2= (001)2 = 1

  • useful in masks; masked_bits = bits & mask

OR ( | ): Bitwise OR is also a binary operator that operates on two equal-length bit patterns, similar to bitwise AND. If both bits in the compared position of the bit patterns are 0, the bit in the resulting bit pattern is 0, otherwise 1.
A = 5 = (101)2 , B = 3 = (011)2
A | B = (101)2 | (011)2 = (111)2 = 7

  • useful in combinition bits on different position b’100’ | b’10’ = b’110’ (think about bit-wise iteration)

XOR ( ^ ): Bitwise XOR also takes two equal-length bit patterns. If both bits in the compared position of the bit patterns are 0 or 1, the bit in the resulting bit pattern is 0, otherwise 1.
A = 5 = (101)2 , B = 3 = (011)2
A ^ B = (101)2 ^ (011)2 = (110)2 = 6

XOR 异或
异或：相同为0，不同为1。也可用「不进位加法」来理解。

异或操作的一些特点：

  • x ^ 0 = x
  • x ^ 1s = ~x // 1s = ~0
  • x ^ (~x) = 1s
  • x ^ x = 0 // interesting and important!
  • a ^ b = c => a ^ c = b, b ^ c = a // swap
  • a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c // associative

Left Shift ( << ): Left shift operator is a binary operator which shift the some number of bits, in the given bit pattern, to the left and append 0 at the end. Left shift is equivalent to multiplying the bit pattern with 2k ( if we are shifting k bits ).
1 << 1 = 2 = 21
1 << 2 = 4 = 22 1 << 3 = 8 = 23
1 << 4 = 16 = 24
…
1 << n = 2^n
将x最右边的n位清零 x & (~0 << n)
获取x的第n位值(0或者1) x & (1 << n)
获取x的第n位的幂值 (x >> n) & 1
仅将第n位置为1 x | (1 << n)
仅将第n位置为0 x & (~(1 << n))
将x最高位至第n位(含)清零 x & ((1 << n) - 1)
将第n位至第0位(含)清零 x & (~((1 << (n + 1)) - 1))
仅更新第n位，写入值为v; v为1则更新为1，否则为0 mask = ~(1 << n); x = (x & mask) | (v << i)

last digit: x & -x
x is a power of 2 then x & (x-1) will be 0.
image

Right Shift ( >> ): Right shift operator is a binary operator which shift the some number of bits, in the given bit pattern, to the right and append 1 at the end. Right shift is equivalent to dividing the bit pattern with 2k ( if we are shifting k bits ).
4 >> 1 = 2
6 >> 1 = 3
5 >> 1 = 2
16 >> 4 = 1

Tricks

We can harness the fact that XOR is its own inverse to find the missing element in linear time.

Because we know that nums contains nn numbers and that it is missing exactly one number on the range [0..n-1][0..n−1], we know that nn definitely replaces the missing number in nums. Therefore, if we initialize an integer to nn and XOR it with every index and value, we will be left with the missing number. Consider the following example (the values have been sorted for intuitive convenience, but need not be):

  • count number of 1 Bits

repeatedly flip the least-significant 1-bit of the number to 0, and add 1 to the sum. As soon as the number becomes 0, we know that it does not have any more 1-bits, and we return the sum.

Questions

Single Numbers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# XOR to find number appears once
def singleNumber(self, nums):
    """
    Given a non-empty array of integers, every element appears twice except for one. Find that single one.
    """
    return reduce(lambda x, y: x^y, nums)
# Mimic three-order in bitwise method
def singleNumber_3(self, nums):
    """
    Given a non-empty array of integers, every element appears three times except for one, which appears exactly once
    """
    one = 0
    two = 0
    three = 0
    for i in range(0,len(nums)):
        two |= one & nums[i] #当新来的为0时，two = two | 0，two不变，当新来的为1时，（当one此时为0，则two = two|0，two不变；当one此时为1时，则two = two | 1，two变为1
        one ^= nums[i]       #新来的为0，one不变，新来为1时，one是0、1交替改变
        three = one & two    #当one和two为1是，three为1（此时代表要把one和two清零了）
        one &= ~three        #把one清0
        two &= ~three        #把two清0
    return one
# xor + low bit
def singleNumber_2(self, nums):
    """
    given nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
    """
    xor = reduce(lambda x, y : x ^ y, nums)
    lowbit = xor & -xor # lowbit的含义为xor从低位向高位，第一个非0位所对应的数字
    # 例如假设xor = 6（二进制：0110），则-xor为（二进制：1010，-6的补码，two's complement） 则lowbit = 2（二进制：0010）
    a = b = 0
    for num in nums:
        # a & lowbit与b & lowbit的结果一定不同.而其他元素相同且出现两次相消，这样可以将a与b拆分开来
        if num & lowbit:
            a ^= num
        else:
            b ^= num
    return [a, b]

Get sum

1
2
3
4
5
6
7
8
9
# a ^ b 直接算出a + b 每位上%2的结果， 进位的话可以直接 (a & b)<<1得到（只有两个位均为1才会进位嘛，左移表示进到下一位啊）
# https://www.hrwhisper.me/leetcode-sum-two-integers/
def getSum(self, a, b):
    MOD     = 0xFFFFFFFF
    MAX_INT = 0x7FFFFFFF
    while b != 0:
        # b is carry
        a, b = (a ^ b) & MOD, ((a & b) << 1) & MOD
    return a if a <= MAX_INT else ~(a & MAX_INT) ^ MAX_INT

Reference