Bitwise

• Bit hacks 

Size of integers in C++

• from stackoverflow 
• All that the standard requires is that:
  • sizeof(char) == 1
  • sizeof(char) <= sizeof(short) <= sizeof(int) <= sizeof(long) <= sizeof(long long)
  • (and that the corresponding unsigned types have the same size as the signed types).
• On 16 bit platforms, it is usual for both short and int to be 16 bits;
• on 32 bit platforms, int and long are almost always the same size.
• On modern 64 bit platforms (with byte addressing), the rational solution would be to make all four types have different sizes (although one could argue that according to the standard, int should be 64 bits, which would mean that int, long and long long all had the same size).
• MS choose to make long 32 bits even on a 64-bit system is that the existing Windows API, for historical reasons use a mixture of int and long for similar things, and the expectation is that this is s 32-bit value (some of this goes back to times when Windows was a 16-bit system). So to make the conversion of old code to the new 64-bit architecture, they choose to keep long at 32 bits, so that applications mixing int and long in various places would still compile.

Two’s complement

1 000   -8
1 001   -7
1 010   -6
1 011   -5
1 100   -4
1 101   -3
1 110   -2
1 111   -1

0 000   0
0 001   1
0 010   2
0 011   3
0 100   4
0 101   5
0 110   6
0 111   7

Reset the last/rightmost set bit: x & (x - 1)

• I think the way to think about it is that for any number x, say, x = 4 (0100), x - 1 will always set all the LSB’s below the lowest set bit and clear the lowest set bit (e.g. 4 - 1 = 3 = 0011.
• quicker way to count bits set with this trick… (only needs set_bit of iteration instead of scan the full 32 bits)

unsigned int v = someinput_val; // count the number of bits set in v
unsigned int cnt = 0; // c accumulates the total bits set in v
for (; v; cnt++)
{
  v &= v - 1; // clear the least significant bit set
}

Detect is power of 2: (x & (x - 1)) == 0

• power of 2 only have one set bit, reset last setbit equal to 0 means it’s power of 2!

Get the last/rightmost set bit: x - (x & (x - 1))

• y = x & (x - 1) remove the last set bit of x
• so x - y return a number with the rightmost set bit
• if you need the position - log2(x - y)

Isolate the least significant bit: x & (-x)

-x = 2’s complement of x = (a1b)’ + 1
   = a’0b’ + 1
   = a’0(0...0)’ + 1
   = a’0(1...1) + 1
   = a’1(0...0)
   = a’1b

        a  1 b     ->  X
&       a' 1 b     -> -X
-----------------
=  (0...0) 1 (0...0)   ---> e.g. we get the LSB through X & (-x)

Detect if two integers have opposite signs: f = (X ^ Y) < 0

• quicker than f = x * y < 0

Common mask

• 0x5 == 0101

• 0xA == 1010

• 0x3 == 0011

• 0xC == 1100

• 0x0 == 0000

• 0xF == 1111

• Reversing the bits in integer

x = ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1);
x = ((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2);
x = ((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4);
x = ((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8);
x = ((x & 0xffff0000) >> 16) | ((x & 0x0000ffff) << 16);

• Conceptually …
  • ABCD -> ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1) -> BADC
  • BADC -> ((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2) -> DCBA

Bitwise rounding to pow of 2 (useful for memory alignment): size = (size + alignment-1) & ~(alignment-1)

• Reference 

Round-up: size = (size + alignment-1) & ~(alignment-1)

Round-down: size &= ~(alignment-1)

Round up reasoning (same for round-down):

Say alignment is 4, which means we want size to be multiply of 4.

4 in binary is 100, any value aligned to 4-byte boundaries (i.e. a multiple of 4) will have the last two bits set to zero.

3 in binary is 11, and ~3 is the bitwise negation of those bits. Performing a bitwise AND with that value will keep every bit the same, except the last two which will be cleared. This gives us a the next lower or equal value that is a multiple of 4.