Comment on page

# 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
}