A = 60 (0011 1100 binary) and B = 13 (0000 1101 binary) → a bit holds a
&
Binary AND copies a bit to the result if it exists in both operands
A & B = 12 (0000 1100)
|
Binary OR copies a bit if it exists in either operand
A | B = 61 (0011 1101)
^
Binary XOR (exclusive OR) copies the bit if it is set in one operand but
not both
A ^ B = 49 (0011 0001)
~
Binary One’s Complement flip bits
~A = ~(60) = (1100 0011)
<<
Binary Left Shift moves the left operand value by the number of bits
specified by the right operand
Left-shifting k bits equals multiplying the bit pattern by 2^k
A << 2 = 240 (1111 0000)
>>
Binary Right Shift
Right-shifting k bits equals dividing the bit pattern by 2^k (omitting
the remainder)
B >> 3 = 1 (0000 0001)
Trick: find the average of two integers fast and not exceed the limit of
the int data type
-
Binary Two’s Complement flip bits and add 1 to the result → ~ then + 1
-A = -60 = (1100 0011) + 1 = (1100 0100)
Algorithms - Check if a given number x is a power of 2 - x = 2^k - Note
that the binary representation of x can only have the form 1000000… - The
binary representation of x - 1 will then be 011111… - x & (x - 1) =
000000… for x = 2^k - Note that 0 itself is not a power of 2 - Count the
number of 1’s in the binary representation of a given number x - x & (x - 1)
reduces the number of 1’s in x by 1 → keep track of that - Keep doing that
while x > 0 - Check if the ith bit is set in the binary form of a given
number x - 2^i binary representation will only have one 1 at the ith bit -
x & 2^i will yield - 0 → the ith bit is not set (0) in x - Non-zero → the
ith bit is set (1) in x - Generate all the possible subsets of a set - A bit
corresponds to an element - 1 denotes the presence of that element in the
subset, while 0 means the absence
Find the largest power of 2 (the most significant bit in binary form), which
is less than or equal to the given number N
N is represented in binary as 1XXXX… → the largest power of 2 is
represented as 10000…
Idea: Transform all bits to the right of the most significant bit to 1, add
1 to the result, and shift right by 1 bit (divide by 2) to obtain the result
Transform bits to 1 by “infecting” bits starting from the most significant
bit - N = N | (N >> 1) to copy the most significant bit to its adjacent
right side - N = N | (N >> 2) to copy the 2 rightmost set bits to their
adjacent right side - N = N | (N >> 4) - N = N | (N >> 8) → all 16
bits have been “infected” → all bits of the long data type (16 bit integer)
→ type-dependent “infection”
Bit manipulation tricks
Obtain binary representation of x - 1 by flipping all the bits to the right
of the rightmost 1 and also the 1
A = 60 (0011 1100), A - 1 = 59 (0011 1011)
The reverse is true, find x + 1 by flipping all the bits to the right of
the rightmost 0 and also the 0
2^k can be written as 1 << k = 1 * 2^k
Return the rightmost 1 in binary representation of x
x ^ (x & (x - 1))
x & (x - 1) will have all the bits equal to x except for the rightmost 1
The bitwise XOR with x will return the rightmost 1
Another solution
x & (-x)
Return the number x with the nth bit set
x | (1 << n)
Return the number x with the nth bit unset
x & (~(1 << n))
Get bit at nth position
(x >> n) & 1
Flip bit at nth bit
x ^ (1 << k)
Fast modulus divisor of power of 2 - x % 2^k = x & (2^k - 1)
Backtracking
Kadane’s algorithm
Divide and Conquer
Number Theory I
Congruence relation: Nếu 2 số nguyên a và b cùng chia cho m và có số dư
giống nhau thì a và b gọi là đồng dư theo module m
Tính chất modulo - Phép cộng - (a + b) mod m = ((a mod m) + (b mod m)) mod
m - Phép trừ - (a - b) mod m = ((a mod m) - (b mod m)) mod m - Phép nhân -
(a * b) mod m = ((a mod m) * (b mod m)) mod m - Phép chia - (a / b) mod m
