Notes on Bitwise

- The bit wise Complement
Note that ~ and ! cannot be used interchangeably. When you take the logical NOT of a non-zero number, you get 0 (FALSE). However, when you twiddle a non-zero number, the only time you'll get 0 is when every bit is turned on. (This non-equivalence principle holds true for bitwise AND too, unless you know that you are using strictly the numbers 1 and 0. For bitwise OR, to be certain that it would be equivalent, you'd need to make sure that the underlying representation of 0 is all zeros to use it interchangeably. But don't do that! It'll make your code harder to understand.)


Now that we have a way of flipping bits, we can start thinking about how to turn off a single bit. We know that we want to leave other bits unaffected, but that if we have a 1 in the given position, we want it to be a 0. Take some time to think about how to do this before reading further.


We need to come up with a sequence of operations that leaves 1s and 0s in the non-target position unaffected; before, we used a bitwise OR, but we can also use a bitwise AND. 1 AND 1 is 1, and 0 AND 1 is 0. Now, to turn off a bit, we just need to AND it with 0: 1 AND 0 is 0. So if we want to indicate that car 2 is no longer in use, we want to take the bitwise AND of XXXXX1XX with 11111011.


How can we get that number? This is where the ability to take the complement of a number comes in handy: we already know how to turn a single bit on. If we turn one bit on and take the complement of the number, we get every bit on except that bit:

~(1<<position)

Now that we have this, we can just take the bitwise AND of this with the current field of cars, and the only bit we'll change is the one of the car_num we're interested in.

int set_unused(int car_num)
{
in_use = in_use & ~(1<<position);
}

- XOR
You might be thinking to yourself, but this is kind of clunky. We actually need to know whether a car is in use or not (if the bit is on or off) before we can know which function to call. While this isn't necessarily a bad thing, it means that we do need to know a little bit about what's going on. There is an easier way, but first we need the last bitwise operator: exclusive-or.
When you take A XOR 0, then you always get A back: if A is 1, you get 1, and if A is 0, you get 0. On the other hand, when you take A XOR 1, you flip A. If A is 0, you get 1; if A is 1, you get 0.
Additionally, if you apply the XOR operation twice -- say you have a bit, A, and another bit B, and you set C equal to A XOR B, and then take C XOR B: you get A XOR B XOR B, which essentially either flips every bit of A twice, or never flips the bit, so you just get back A. (You can also think of B XOR B as cancelling out.) As an exercise, can you think of a way to use this to exchange two integer variables without a temporary variable? (Once you've figured it out, check the solution.)

Write an Efficient C Program to Reverse Bits of a Number

See link: http://geeksforgeeks.org/?p=726#comment-1637

Method1 – Simple
Loop through all the bits of an integer. If a bit at ith position is set in the i/p no. then set the bit at (NO_OF_BITS – 1) – i in o/p. Where NO_OF_BITS is number of bits present in the given number.

/* Function to reverse bits of num */ unsigned int reverseBits(unsigned int num) {     unsigned int  NO_OF_BITS = sizeof(num) * 8;     unsigned int reverse_num = 0, i, temp;     for (i = 0; i < NO_OF_BITS; i++)     {         temp = (num & (1 << i));         if(temp)             reverse_num |= (1 << ((NO_OF_BITS - 1) - i));     }     return reverse_num; } /* Driver function to test above function */ int main() {     unsigned int x = 2;     printf("%u", reverseBits(x));     getchar(); }

Above program can be optimized by removing the use of variable temp. See below the modified code.

unsigned int reverseBits(unsigned int num) {     unsigned int  NO_OF_BITS = sizeof(num) * 8;     unsigned int reverse_num = 0;     int i;     for (i = 0; i < NO_OF_BITS; i++)     {         if((num & (1 << i)))            reverse_num |= 1 << ((NO_OF_BITS - 1) - i);    }     return reverse_num; }

Time Complexity: O(log n)
Space Complexity: O(1)

Method 2 – Standard
The idea is to keep putting set bits of the num in reverse_num until num becomes zero. After num becomes zero, shift the remaining bits of reverse_num.
Let num is stored using 8 bits and num be 00000110. After the loop you will get reverse_num as 00000011. Now you need to left shift reverse_num 5 more times and you get the exact reverse 01100000.

unsigned int reverseBits(unsigned int num) {     unsigned int count = sizeof(num) * 8 - 1;     unsigned int reverse_num = num;     num >>= 1;     while(num)     {        reverse_num <<= 1;        reverse_num |= num & 1;        num >>= 1;        count--;     }     reverse_num <<= count;     return reverse_num; } int main() {     unsigned int x = 1;     printf("%u", reverseBits(x));     getchar(); }

Time Complexity: O(log n)
Space Complexity: O(1)

Method 3 – Lookup Table:
We can reverse the bits of a number in O(1) if we know the size of the number. We can implement it using look up table. Go through the below link for details. You will find some more interesting bit related stuff there.
http://www-graphics.stanford.edu/~seander/bithacks.html#BitReverseTable

Related Posts

• Compute the integer absolute value (abs) without branching
• Compute modulus division by a power-of-2-number
• Compute the minimum or maximum of two integers without branching
• Rotate bits of a number
• Find the two non-repeating elements in an array of repeating elements
• Count number of bits to be flipped to convert A to B
• Count set bits in an integer

Method 4 – Swap:
Another way is to swap the bits in a 2^n hierachcal procedule:

For the 32bit number, do

• Swap adjacent bits in the word, i.e. bit position pairs are (0, 1), (2, 3)…(28, 29), (30, 31).
• Swap adjacent 2 bits in the word, i.e. bit position pairs are (01, 23), (45, 67)…
• Swap adjacent 4 bits in the word
• Swap adjacent 8 bits in the word
• Swap adjacent 16 bits in the word

The swap can be done by the following:


The following  page gives  metho for swap the 8 bits:
swap the first 4-bits of a number with the last 4 bit. (eg. 1011 1110 should be 1110 1011.)
http://stackoverflow.com/questions/1192487/swap-bits-in-a-number-in-c
unsigned char c;
c = ((c & 0xf0) >> 4) | ((c & 0x0f) << 4);


Method 5 – Do the mask:
For ex :
I/P  =   10111010 10111010 10111010 10111010
O/P =  01011101 01011101 01011101 01011101


Solution
The above mentioned solution can be tackled by the following manner :

• Iterate over all the bits of the number
• Create masks that can be used to extract the bits present at left / right positions ( ex : 00000000000000000000000000000001 , 10000000000000000000000000000000  etc )
• Perform bitwise AND of the number with the above mentioned masks , this will obtain the bits that we need to reverse and store them in two variables.
• Set the two bit locations in X to 0
• shift the variables in step 3 appropriately so that they move the the positions where we set a 0
• do a bitwise OR operation
• shift the masks appropriately 
• Once the loop is over , we are done..

Code Snippet : 

#define INT_SIZE_BITS 32

unsigned int reverseBits( unsigned int x )
{
    unsigned int mask1 = 1; 
    unsigned int mask2 = 1 << (INT_SIZE_BITS - 1);
         
    int step = INT_SIZE_BITS - 1 ;  
         
    while( step > 0 )
    {
     // obtaining the left and right bits 
             
        unsigned int rightBit = x & mask1;
        unsigned int leftBit = x & mask2;
             
        // clearing out the left and right bits 
        x = x & ( ~mask1) & ( ~mask2);
  // shifting the bits to point to appropriate positioin
        unsigned int mask3 = rightBit << step;
        unsigned int mask4 = leftBit >> step;
  // setting the bits appropriately
        x = x | mask3 | mask4;
        
  // Updating the masks
        mask1 = mask1 << 1;
        mask2 = mask2 >> 1;
             
        step = step - 2;
    }
    return x;
}

=======================
(note that the step is very important, using this control, we could swap the pair, and totally using n/2 steps.)
to make the code clear, we can just use:

for (step = 0; step < total_length/2; step ++)
{
    bitpeek_left = 1<< (total_length - step+ 1)
    bitpeek_right = 1<< step

      left_bit = (x & bitpeek_left) >> (total_length - step+ 1);    \\ get whether it is 1 or 0
      right_bit = (x & bitpeek_right) >> step;    \\ get whether it is 1 or 0

     if (left_bit != right_bit)
   {
     mask_left =  left_bit << (total_length - step+ 1);
     x =   x & (~ bitpeek_left);     \\ get the original place to be zero
     x =   x |  (mask_left);

     mask_right =  right_bit << ( step);
     x =   x & (~ bitpeek_right);     \\ get the original place to be zero
     x =   x |  (mask_right);
   }
}

==== Another very good one =====
From: http://20bits.com/articles/interview-questions-counting-bits/


Just know the background of such problem:
The setup usually goes something like this. We’re receiving gigabytes of data per second. Each chunk of data comes with a header that contains an unsigned 32-bit integer. Let’s call that integer the routing number. We choose the routing destination based on the number of on bits in the binary representation of the routing number.
Write a routine that returns the number of on bits in the binary representation of an unsigned 32-bit integer in C.

The basic:

int bitcount(unsigned int n) {
    int count = 0;  
    while (n) {
        count += n & 0×1u;
        n >>= 1;
    }
    return count;
}

The author has another advanced one:

Pre-computation

Since speed was a requirement something that takes linear time is probably a bad idea. The key idea is to realize that a deterministic function, like bitcount, is no different than a hash where the keys are the inputs to the function and the values are the output of the function.
This is principle behind memoization, for example, but here we’re sitting pretty. Since both the input and output are unsigned integers we can create a regular array, call it bit_table, where bit_table[i] is the number of on bits in the binary representation of i.
Furthermore since we have the constraint that the integer is 32-bits we can, in theory, pre-compute the entirety of bit_table and include it in a header. It’d work like this:

// Pre-compute this elsewhere and put it here.
static unsigned int bit_table32[0×1u << 32];

int bitcount_32(unsigned int n) {
    return bit_table32[n & 0xFFFFFFFFu];
}

♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥