Working with Bitwise Operators

Discussion in 'C' started by Trinity, Oct 29, 2012.

  1. Trinity

    Trinity New Member

    Joined:
    Nov 23, 2011
    Messages:
    28
    Likes Received:
    11
    Trophy Points:
    3
    Occupation:
    Software Engineer
    As it is said, great things are in small ones. Its someway true in C as well. Working on bits rather than bytes, and other bigger data structures leverage implementations in speed and space efficiency. With really high end computers coming up these days, bitwise operations may not be that useful in terms of space efficiency. However, certain bitwise operators do pace up the speed of the implementation. Moreover, considering embedded systems programming, memory is really a paramount factor in optimisations. Hence, bitwise operators and operations are really helpful in such embedded systems programming environment.

    To get a know how of the basics, lets understand basic bitwise operators and how they work. First of all, one should be aware of the binary representation of numbers and two’s complement.

    AND (&) Operator

    The AND operator works on two 1-bit operands such that, only if both are 1, it results as 1, else it results as 0.

    For Example:
    Code:
    101 & 110 = 100
    
    OR (|) Operator

    The OR Operator works on 1-bit operands such that, if any of the two is 1, it results as 1, else it results as 0.

    For Example:
    Code:
    101 & 110 = 111
    
    XOR (^) Operator

    The XOR operator works on 1-bit operands such that, if both are 1 or of both are 0, it results as 0, else if any of them is 1 and other is 0, it results as 1.

    For Example:
    Code:
    101 & 110 = 011
    
    Left Shift(<<) Operator

    It is a one operand operator. The Left shift operator works on a set of bits i.e a number represented by ‘n’ bits, and when shifted by an operand ‘k’, it shifts its ‘k’ bits towards left by ‘k’ replacing the trailing bits with zeros.

    For Example:
    Code:
    001<<1 = 010
    
    Right Shift(>>) Operator

    It is a one operand operator. The Right shift operator works on a set of bits i.e a number represented by ‘n’ bits, and when shifted by an operand ‘k’, it shifts its ‘k’ bits towards right by ‘k’ bits replacing front bits with zeros.

    For Example:
    Code:
    010>>1 = 001
    
    Not (~) Operator

    The Not Operator is a one operand operator, which just toggles every bit of the n-bits number.

    For Example:
    Code:
    ~(010) = 101
    
    To summarize all the bitwise operators in a table:

    [​IMG]

    Some common scenarios to use bitwise operators



    There are many cases and scenarios where bitwise operators are really helpful. It is not that, bitwise operators are needed to be used, its only because they make the implementation efficient, hence they are preferred. Worth mentioning, for all such scenarios, it works for negative numbers as well, which are represented in the two’s complement in the binary representation. However, the two’s complement representation itself takes care of it. So, most of the bitwise operations and tricks work fine for negative numbers as well.

    Multiply or divide by two

    Consider a multiplication operation, it involves reading registers, and then applying the multiplier to the two registers at the low level. Division is even more expensive operation. However, when the multiplication or division is by a number which is power of 2, it can be much optimized using shift operators. Shift bitwise operations are much efficient at low levels.
    For example:
    Code:
    //In Binary,
    00000001 << 1 = 00000010
    
    // In decimal
    1<<1 = 2
    
    The above computation simply multiplies the number by 2, which shifted by 1. Hence, every left shift of ‘k’ bits, multiplies the number by 2 raise to the power k. Similarly, every right shift by ‘k’ bits divides the number by 2 raise to the power k.
    This is a very common optimization trick used in bitwise operations

    Determine if a number is power of 2

    Here we have a problem, where we need to devise an algorithm to determine if the inputted number is a power of 2 or not. To start with an example, like 2, 4, 8, etc.
    There may be a number of solutions to it using loops, conditionals. Lets just think about it at bit level. Write down the binary representation of positive result values, and observe the pattern
    Code:
    2 -> 00000010
    4 -> 00000100
    8 -> 00001000
    
    Note, in all the numbers which are power of 2, it consists of just one 1, which is followed by all trailing zeros. One solution to think of could be, count the number of 1’s in the binary representation and if this count equals to 1, then the number is a power of 2.

    Still, this solution would include a loop, to count the number of 1’s in the number. There could be a better way out, as we just need to check if number has just one 1.
    Understanding binary representations, and its patterns in which they increment, note how 2, 4 or 8 are reached.
    Code:
    00000000
    00000001
    00000010
    00000011
    00000100
    00000101
    00000110
    00000111
    00001000
    
    Note, starting from the least significant bit, it starts incrementing the bits i.e. from 0 to 1. Once, it reached 1, it increments the next least significant bit and starts the loop for it with all exhausted (following bits) bits as 0. Therefore, for all, exhausted sets of bits, the next following number would be, one 1 at next least significant bit with all trailing zero’s. Hence, just one 1. To understand the other way round, for all numbers, which are a power of 2, the next decremented number would be all 1’s following least significant bits. As in,
    Code:
    00000001 ---> 00000010
    00000011 ---> 00000100
    00000111 ---> 00001000
    
    Therefore, AND-ing a number x with one lesser, i.e. (x-1), if that results in a zero, that means the number is a power of 2. This solution looks quite efficient and elegant as well.

    Programmatically,
    Code:
    if (x & (x-1))
    {
        printf(“The number is not a power of two\n”);
    }
    else
    {
        printf(“The number is a power of two\n”);
    }
    
    Determine if integer is odd or even

    Most of the efficient bit manipulation algorithms comes through observing the binary representation patterns. Lets do the same here. Lets observe the binary pattern for odds and even numbers. First the even numbers:
    Code:
    00000000
    00000010
    00000100
    00000110
    00001000
    00001010
    00001100
    00001110
    
    Lets write down the first few odd numbers in binary. First the even numbers:
    Code:
    00000001
    00000011
    00000101
    00000111
    00001001
    00001011
    00001101
    00001111
    
    Did you note? Yes, for even numbers, it always ends with a 0, while an odd number always ends with a 1. To determine, the ending bit is 1 or 0, we just need to AND our number with the number 1, and if it results with a 1, that means it was an odd. However, if ANDing with 1 results in zero, then it means the ending bit of the number was 0, and hence it is an even number.

    For example. Lets take any even number of 1 byte. We are keeping first 7 bits as ‘x’ that is as don’t care. The ending bit i.e. the least significant bit is 0.
    Code:
    xxxxxxx0
    &
    0000001
    -------------
    00000000 
    -------------
    
    Now, lets confirm our solution algorithm with an odd number of 1 byte. Again, we’ll keep most significant 7 bits as ‘x’ i.e. don’t care, and the least significant bit as 1.
    Code:
    xxxxxxx1
    &
    0000001
    -------------
    00000001 
    -------------
    
    The solution code would look like
    Code:
    if (num & 1)
    {
        printf(“The number is ODD\n”);
    }
    else
    {
        printf(“The number is EVEN\n”);
    }
    
    Set/Unset kth Bit

    To set a bit, we just need to OR it with 1, and to unset a bit, we can AND it with 0. What about in a 1-byte or 4-byte number, we want to set/unset the kth bit. We need to compute the operand with which we need to OR or AND the number.

    Here is a way to do that.

    To set the 3rd bit, lets take our number with all bits as don’t care except 3rd
    Code:
    x x x x x 0 x x x
    |
    0 0 00 0 1 0 0 0
    -------------------------
    x x x x x 1 x x x
    -------------------------
    
    Now, to unset the 3rd bit, lets take our number with all bits as don’t care except 3rd
    Code:
    x x x x x 1 x x x
    &
    1 1 11 1 0 1 1 1
    -------------------------
    x x x x x 0 x x x
    -------------------------
    
    In a program, it looks like, To set the kth bit,
    Code:
    res = num | (1<<k);
    
    To unset the kth bit,
    Code:
    res = num & ~(1<<k)
    
     
    Last edited by a moderator: Jan 21, 2017
    grizlizli likes this.
  2. grizlizli

    grizlizli New Member

    Joined:
    Dec 26, 2012
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Studying
    Location:
    Belgrade, Serbia
    Nice one...

    Can you tell me where I may use bitwise operators except for multiplication/division by power of 2 or determining if integer is odd or even?
    I mean in real life situation...
     
  3. iranjit

    iranjit New Member

    Joined:
    Jan 5, 2013
    Messages:
    4
    Likes Received:
    2
    Trophy Points:
    0
    Home Page:
    http://www.programiz.com
    I have only used bit-wise operators in programming of embedded system.
     
    grizlizli likes this.
  4. Trinity

    Trinity New Member

    Joined:
    Nov 23, 2011
    Messages:
    28
    Likes Received:
    11
    Trophy Points:
    3
    Occupation:
    Software Engineer
    Thanks.

    Well, bitwise operations are the like blood in embedded programming, as one needs to account for every bit stored. Even in video/audio parsing, where raw data is being parsed and decoded, bitwise operations are of great help.
    Hope that helps.
     
    grizlizli and shabbir like this.
  5. grizlizli

    grizlizli New Member

    Joined:
    Dec 26, 2012
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Studying
    Location:
    Belgrade, Serbia
    All right.

    I have learn it in college but no one told us what's the use of bitwise operators in praxis.
    Now I can get the idea. Thanks.

    P.S. I would appreciate it if someone else shared his experience.
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice