BitWise Operators - Basic Tutorial

In this article we will discuss about the bitwise operators and their application in practical applications with some examples with required explanation. For simplicity lets stick to C/C++ for this article. The lowest level of data that we can access is 'byte' and by convention a 'byte' contains 8 bits. A 'bit' can represent two different values - 0 and 1. To represent larger values we need collection of bits.


* Bits and HexaDecimal Values
   Hexadecimal values contains numbers from 0..9 and then A...F where A=10, B=11 and so on. Thus 0-15 can be represented in hex values from 0-F. To represent values from 0-15, we require 4 bits. Thus to represent a byte in hex values we ultimately require 2 hexadecimal literals. eg.
  128 in integer == 1000 0000 in binary == 80 in hex OR 0x80 (0x or 0X is used as a prefix to reresent hex values).
 
* BitWise Operators in C

  There are six bitwise operators. They are:
   &   The AND operator
   |   The OR operator
   ^   The XOR operator
   ~   The Ones Complement or Inversion operator
  >>   The Right Shift operator
  <<   The Left Shift operator.


  
Hoping that every body is familiar with these operators, hence I am not going to explain the operator and their boolean truth table. Instead lets focus on their application and some good use cases:


* Test whether a particular bit is SET
  //check whether 5th bit is set or not in integer value - 50. (count right most bit as the 1st bit.)

  int temp = 50; // 0011_0010
  if (temp & 0x10) {
    // bit 5 is SET
  }

 
* To Set a Particular 'bit'
  //set 3rd bit in an integer with value 50.
  int temp = 50; // 0011_0010
  temp = temp | 0x04; //0x04 == 0000_0100

  Result :: temp -> 0011_0110


* Toggle bits in an integer
  //toggle bit no. 2 from an integer with value - 6.

  int temp = 6; //0000_0110
  temp = temp ^ 0x0a   //0000_1010

 
  This will toggle the 2nd from '1' to '0' and 4th bit from 0 to 1.
  Result :: temp -> 0000_1100
 
* Reset a Particular 'bit'
  //reset bit no. 2 from integer with value 50.
  int temp = 50 // 0011_0110
  temp = temp & ~0x02 // ~0x02 -> ~(0000_0010) -> 1111_1101

 
  Result :: temp -> 0011_0100
 
*multiply by 2n
  int mult_by_pow_2(int value, int pow)
  {
    return value << pow;
  }

 
  Shifting right a number by 1 effectively multiplies the given number by 2.

  Explanation: 4 << 1 -> 0000_0100 << 1 -> 0000_1000 (i.e. '8')

 
* Finding the bit in 'nth' position is set or not
  int temp = 50 // 0011_0110
  char pos = 5  // bit postion we are interested in.
  char res;
 
  res = temp & (1 << pos-1);

 
  Explanation: shifting '1' with 'pos' we are guaranteed to have only a single bit on with all bits as 0, and we know it's to the far-right. Afterwards, the '&' operator will be used to find the particular bit is SET/RESET.


* Check whether a number is power of 2

  int is_pow2(int x) {
    return !(x & (x-1));
  }

 
  Explanation: A number that is Power of 2 has only a single 'bit' SET. eg. 01000000. Now, doing a (x-1) operation on this values yields all bits set to 1 with the already set bit to 0.

  01000000 - 00000001 = 00111111

  
  Now, applying an AND operator with the original value  leaves us with all bits reset to 0.
  01000000 & 00111111 = 00000000.
 
  Note: 0 as a value is not actually considered as power of 2, hence we can modify the above condition as following to make it complete:
  
  return (x != 0) && !(x & (x-1));

 
* Calculating the count of SET bits in an integer

    unsigned int v; // count the number of bits set in v

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

    
    Explanation: We have already seen the result of operation (v & (v -1)). This resets the least significant SET bit to 0 in every iteration of while loop. The loop breaks when all the SET bits are reset to 0 and the number of SET bits is the number of iterations of while loop.
 
Keeping it simple, Lets wind up this article here itself. Most of the examples explained above are fairly simple but they find real use in practical scenarios. For more complex examples related to Bitwise Operator, I have a follow-up article BitWise Operators Advanced Tricks .


-Pankaj
Happy Programming

comments powered by Disqus