Binary representation

  • Unsigned bits Each unsigned variants can store numbers from 0 to 2 power of (n) - 1, so a n=8 can store numbers from 0 to 2⁸ - 1, which equals 0 to 255.
  x = 0b10010110
x =  2⁷ + 2⁴ + 2² + 2¹
x = 128 + 16 +  4 +  2
x = 150
  
  x = 0b11111111
x = 2⁷  + 2⁶ + 2⁵ + 2⁴ + 2³ + 2² + 2¹ + 2⁰
x = 128 + 64 + 32 + 16 + 8  + 4  + 2  + 1
x = 255
x = 256 - 1
x = 2⁸  - 1
  • Signed bits Each signed variant can store numbers from -2 power of (n-1) to 2 power of (n-1) - 1 inclusive, where n is the number of bits that variant uses. So an n=8 can store numbers from -(2⁷) to 2⁷ - 1, which equals -128 to 127.
  x = 0b10010110
x = -( 2⁷) + (2⁴ + 2² + 2¹)
x = -(128) + (16 +  4 +  2)
x = -(128) + (22)
x = -106
  
  x = 0b11111111
x = -(2⁷ ) + (2⁶ + 2⁵ + 2⁴ + 2³ + 2² + 2¹ + 2⁰)
x = -(128) + (64 + 32 + 16 + 8  + 4  + 2  + 1 )
x = -(128) + (127)
x = -1

Ones’ complement

  • The ones’ complement of a binary number is the value obtained by flipping all the bits in the binary representation of the number.

Equivalent to NOT bitwise operator.

  x  = 0b10010110
~x = 0b01101001
  • The name “ones’ complement” refers to the fact that such an flipped value, if added to the original, would
  x + ~x = 0b11111111

Two’s complement

  • The two’s complement of a binary number is the ones’ complement to which we add 1.
  y = ~x + 1

Equivalent to - (binary number).

  x + ~x  = -1
    -x  = ~x + 1
  
   x  = 0b00010110
~x  = 0b11101001
-x  = 0b11101010
  
   x  = 0b01101100
~x  = 0b10010011
-x  = 0b10010100

LSb calculation

  • The LSb (least significant bit) is the bit position in a binary number representing the binary first place of the number.

| Equivalent to the right-most-bit: 0b10010110

  • Complexity
  O(n)
  • Formula
  r = x & (~x + 1)
  
  x              =   0b 101111010110110 1
~x             =   0b 010000101001001 0
~x + 1         =   0b 010000101001001 1
x & (~x + 1)   =   0b 000000000000000 1

Least significant 1

  • Formula
  r = x & (-x)
  
  x           =   0b 00100000010 1 0000
-x          =   0b 11011111101 1 0000
x & (-x)    =   0b 00000000000 1 0000

Set the kth bit

  • Formula
  y = x | (1 << k)
  
  x              =   0b 10111101 0 1101101
1 << k         =   0b 00000000 1 0000000
x | (1 << k)   =   0b 10111101 1 1101101

Clear the kth bit

  • Formula
  y = x & ~(1 << k)

k = 7

  x              =   0b 10111101 1 1101101
1 << k         =   0b 00000000 1 0000000
~(1 << k)      =   0b 11111111 0 1111111
x & ~(1 << k)  =   0b 10111101 0 1101101

Flip the kth bit

  • Formula
  y = x ^ (1 << k)

k = 7

  x              =   0b 10111101 0 1101101
1 << k         =   0b 00000000 1 0000000
x ^ (1 << k)   =   0b 10111101 1 1101101
  
  x              =   0b 10111101 1 1101101
1 << k         =   0b 00000000 1 0000000
x ^ (1 << k)   =   0b 10111101 0 1101101

Extract a bit field

  • Formula
  y = (x & mask) >> shift

shift = 7

  x                   =   0b 10111 1010 1101101
mask                =   0b 00000 1111 0000000
x & mask            =   0b 00000 1010 0000000
(x & mask) >> shift =   0b 000000000000  1010

Set a bit field

  • Formula
  x = (x & ~mask) | ((y << shift) & mask)

shift = 7

  x                                   =   0b 10111 1010 1101101
y                                   =   0b 000000000000  0011
mask                                =   0b 00000 1111 0000000
x & ~mask                           =   0b 10111 0000 1101101
(x & ~mask) | ((y << shift) & mask) =   0b 10111 0011 1101101

Swap with no-temporary variable

  • Formula
  x = x ^ y
y = x ^ y
x = x ^ y
  
  x           =   0b 10111101
y           =   0b 00101110
x = x ^ y   =   0b 10010011
y = x ^ y   =   0b 10111101
x = x ^ y   =   0b 00101110
  • Nota
  (x ^ x)     = 0
(x ^ 0)     = x
(x ^ y) ^ x = y

Minimum of two integers with no-branch

  • Formula
  r = y ^ ((x ^ y) & -(x < y))
  • x < y
  x                   =   0b 00001010
y                   =   0b 00111101
x < y               =    1 (TRUE)
-(x < y)            =   -1
-(x < y)            =   0b 11111111
y ^ ((x ^ y) & -1)  =    x
  • x >= y
  x                  =    0b 00111101
y                  =    0b 00001010
x < y              =     0 (FALSE)
y ^ ((x ^ y ) & 0) =     y

Modulo n

  • Classic formula
  r = (x + y) % n
  • Optimized formula when 0 <= x < n & 0 <= y < n
  z = x + y
r = z - (n & -(z >= n))

Rounding a value to the nearest power of 2

  • Problem
  r = 2 power of (log(2) n)
  • Formula
  n               =   0b 0010000001010000
--n             =   0b 0010000001001111 # In case n is already a power of 2
n |= n >> 1     =   0b 0011000001101111 # Populate all bits to the right with 1
n |= n >> 2     =   0b 0011110001111111 # Populate all bits to the right with 1
n |= n >> 4     =   0b 0011111111111111 # Populate all bits to the right with 1
n |= n >> 8     =   0b 0011111111111111 # Populate all bits to the right with 1
...
n |= n >> 64    =   0b 0011111111111111 # Populate all bits to the right with 1
++n             =   0b 0100000000000000

Log base 2 of a power of 2

  • Problem
  r = log(2) x, where x is a power of 2

deBruijn constant

  • A deBruijn sequence s of length 2 power k is cyclic 0-1 sequence such that each of the 2 power k 0-1 strings of length k occurs exactly once as a substring of s. k = 3
  n   00011101
0   000
1    001
2     011
3      111
4       110
5        101
6         010
7          100

n Queens problem

  • Place n queens on an n * n chessboard so that no queen attacks another.
    => No 2 queens in any row, column, or diagonal.
  backtrackng algorithm