Cracking The Coding Interview/Q 5.5

From Software Engineers Wiki
Jump to: navigation, search

Write a function to determine the number of bits required to convert integer A to integer B.

EXAMPLE

  • Input: 31,14
  • Output: 2

Answer

Do an XOR operation between A and B. For each bit, XOR will set only if the bit value is different in A and B. Then count the number of bits set. Refer to Count Bits with Value 1 regarding how to count bits with bit value 1.

def count_bits_with_value_1(n):
        count = 0
        while (n != 0):
                n &= n - 1
                count += 1
        return count

def count_bits_to_convert(A, B):
        return count_bits_with_value_1(A ^ B)

Test program:

def main():
        print(count_bits_to_convert(0xcccccccc, 0xcccccccc))
        print(count_bits_to_convert(0xcccccccc, 0x33333333))
        print(count_bits_to_convert(0xcccccccc, 0xdddddddd))

main()

Test result:

0
32
8
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox