7. Bit Manipulation

Bitwise Operators

(This part is copied over from Python Wiki)

All of these operators share something in common -- they are "bitwise" operators. That is, they operate on numbers (normally), but instead of treating that number as if it were a single value, they treat it as if it were a string of bits, written in twos-complement binary.

A two's complement binary is same as the classical binary representation for positive integers but is slightly different for negative numbers. Negative numbers are represented by performing the two's complement operation on their absolute value.

x << y

Returns x with the bits shifted to the left by y places (and new bits on the right-hand-side are zeros). This is the same as multiplying x by 2**y.

x >> y

Returns x with the bits shifted to the right by y places. This is the same as //'ing x by 2**y.

x & y

Does a "bitwise and". Each bit of the output is 1 if the corresponding bit of x AND of y is 1, otherwise it's 0.

x | y

Does a "bitwise or". Each bit of the output is 0 if the corresponding bit of x AND of y is 0, otherwise it's 1.

~ x

Returns the complement of x - the number you get by switching each 1 for a 0 and each 0 for a 1. This is the same as -x - 1.

x ^ y

Does a "bitwise exclusive or". Each bit of the output is the same as the corresponding bit in x if that bit in y is 0, and it's the complement of the bit in x if that bit in y is 1. Just remember about that infinite series of 1 bits in a negative number, and these should all make sense.

Two's compliment

The two's complement of an N-bit number is defined as the complement with respect to 2**N; in other words, it is the result of subtracting the number from 2**N. This is also equivalent to taking the ones' complement and then adding one, since the sum of a number and its ones' complement is all 1 bits. The two's complement of a number behaves like the negative of the original number in most arithmetic, and positive and negative numbers can coexist in a natural way.

-- Wikipedia on two's compliment

A two's complement binary is same as the classical binary representation for positive integers but is slightly different for negative numbers.

-- Python Wiki

  • Converting from two's complement representation (to a dec number)

    1. check the leading sign bit(or the most significant bit)
    2. if 1:
      1. flip the bits
      2. add 1 and convert to dec
      3. add "-" sign to the front
    3. if 0:
      1. convert to dec directly

    e.g. convert 1001, leading bit is "1", so

    1. flip the bits: 0110
    2. add 1: 0111
    3. convert to dec, or 7
    4. the number is -7

    e.g. convert 0110: leading bit is "0", so convert it to 6, directly

  # Python code for computing the two's compliment of int value val:
  # Source: http://stackoverflow.com/questions/1604464/twos-complement-in-python

  def twos_comp(val, bits):
      """compute the 2's compliment of int value val"""
      if (val & (1 << (bits - 1))) != 0: # if sign bit is set e.g., 8bit: 128-255
          val = val - (1 << bits)        # compute negative value
      return val                         # return positive value as is

  binary_string = '00011110' # or whatever... no '0b' prefix
  out = twos_comp(int(binary_string,2), len(binary_string))
  print out

  • Converting to two's complement representation (from a dec number)

    1. check the sign
    2. if negative:
      1. flip the bits
      2. add 1 and convert to dec
    3. if positive: convert to binary directly

    e.g. convert -30, a negative int, so

    1. convert to binary: 00011110
    2. flip the bits: 11100001
    3. add 1: 11100010

    e.g. convert 30, a positive int, so convert to 00011110, directly

Problems:

  • LC 371. Sum of Two Integers

    Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -

    Background:

    • Sum of two bits can be obtained by performing XOR (^) of the two bits, e.g 1^1 = 0, and the carry bit can be obtained by performing AND (&) of two bits, e.g. 1 & 1 = 0

  • LC 190. Reverse Bits

    Reverse bits of a given 32 bits unsigned integer. For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

  • LC 89. Gray Code

    The gray code is a binary numeral system where two successive values differ in only one bit.

    Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

Background info: wiki on Gray Code

results matching ""

    No results matching ""