Problem on Bit Operation

  1. Bitwise Addition ORGiven two binary strings, return their sum (also a binary string). GFGCode
    Algo: 
    Sum = a XOR b XOR c
    Carry = (a AND b) OR ( b AND c ) OR ( c AND a )
     

     

  2.  Binary to decimal Code Image
  3.  Decimal to Binary  Code
  4.  [Pending] Add two numbers without using arithmetic operators. GFG  Code
  5. Number of Bits in a d-Digit Decimal Integer.                                     bspec = ⌊log2(n)⌋ + 1
    or    There are floor(lg(N)) + 1 significant bits in N — that’s a base-2 logarithm
    Link for above result.
  6. A number of bitwise operation link that are good to know.
  7. *** Count set bits in an integer
    Algo:
    1. Loop through all bits in an integer, check if a bit is set and if it is then increment
    the set bit count.
    2. Brian Kernighan’s Algorithm takes O(log N). See the above formula for the reason of complexity.
    Subtraction of 1 from a number toggles all the bits (from right to left) till the
    rightmost set bit(including the righmost set bit). So if we subtract a number by 1
    and do bitwise & with itself (n & (n-1)), we unset the righmost set bit. If we do n &     (n-1) in a loop and count the no of times loop executes we get the set bit count.
    If you start with.
                       n = 1010101 & n-1=1010100 => 1010100
    n = 1010100 & n-1=1010011 => 1010000
    n = 1010000 & n-1=1001111 => 1000000
    n = 1000000 & n-1=0111111 => 0000000
    So this iterates 4 times. Each iteration decrements the value in such a way that
    the least significant bit that is set to 1 disappears.
  8. Binary Number with points interpretation.
               Why b101.001 = 5.125?
    b10 = 2^1
    b1 = 2^0
    b0.1 = 2^-1
    b0.01 = 2^-2
    b0.001 = 2^-3 = 0.125
  9. Rotate bits of a number. Code   GFG
    Algo: There are inbuilt method to shift the bits but not rotated the bits. Youtube
  10. Count set bits in an integer. GFG. Code
  11. How would you find the number of bit swaps required to convert integer A to integer B? GFG
    Algo: Use XOR and count the set bit.
  12. How do you find out if an unsigned integer is a power of 2?
    The trick here is to know that an unsigned integer which is a power of 2 has only one of its bits as 1. So a simple solution would be to loop through the bits and count the number of 1s.
  13. Add 1 to a given number without using arithmetic operator. Youtube
Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s