Binary representation link 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 link 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 link 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 link 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 link Formula r = x & (-x) x = 0b 00100000010 1 0000 -x = 0b 11011111101 1 0000 x & (-x) = 0b 00000000000 1 0000 Set the kth bit link 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 link 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 link 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 link 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 link 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 link 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 link 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 link 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 link 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 link Problem r = log(2) x, where x is a power of 2 deBruijn constant link 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 link 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

Posts