Reverse Binary

/**
* Reverse the binary bits of a given integer.
*/

/*
The idea:
 - msb effectively counts the number of bits in a number, since the remaining zero
   the come before the number are basically redundent.
 - the way we do this is by bit shifting the number to the right by 1, everytime
   and the moment the number is zero, means that we have reached the end, (there
   are no more bits to check that are remaining)
 - We add one to msb since when we do (1 << num_digits_2) - 1, that -1 gets rid
   of one bit.
 - all_ones bit shifts 1 to the right to the msb. -1 gets the previous numbers, which
   will always be all ones.

   Ex.
      .         <- msb
   000111010101
   001000000000 <- 1 << num_digits
   000111111111 <- (1 << num_digits - 1)
   000000101010 <- toggle with ^
*/

// actually runs in constant time, O(32)
unsigned msb(int num) 
{
    unsigned count = 0;
    while (num >>= 1)
        count++;
    return count;
}

int rev_binary(int num)
{
    int num_digits_2 = msb(num) + 1;
    int all_ones = (1 << num_digits_2) - 1;
    return num ^ all_ones;
}


/**
* Count the number of bits in a given integer.
* - see msb
*/


int main()
{
    int rev_n = rev_binary(483); 
    cout << rev_n << endl; // 28
}