Cracking The Coding Interview/Q 5.3

From Software Engineers Wiki
Jump to: navigation, search

Given a positive integer, print the next smallest and the next largest number that have the same number of 1 bits in their binary representation.

Answer #1: Brute-force method

Try all numbers and find a number that has same bit count. For some number, this will take a long time to find the number. For example, to find next number, 0x40000000 needs trying all numbers fro 0x40000001 to 0x80000000.

The code is included below.

Answer #2: Bit manipulation

With proper bit manipulation, it can find numbers with same bit count. To find next number with same bit count, let's take some examples

0b01010000 => 0b01100000
0b00100010 => 0b00100110
0b01100000 => 0b10000001

To make a higher number, it needs to find first 0 with trailing 1, then flip the bit. This increase the bit count by one. So it finds next smallest number with one less bit count. So the step is as follows.

  1. Find first bit set from LSB
  2. Find next bit cleared
  3. Flip this bit. This increases the bit count.
  4. Clear all the LSBs until this bit, then add smallest number with one less bit count.

Finding the previous number with same bit count can be done by similar apporach.

0b01010000 => 0b01001000
0b00100010 => 0b00100001
0b00100010 => 0b00100001

The steps are

  1. Find first bit cleared from LSB
  2. Find next bit set
  3. Flip this bit. This reduces the bit count
  4. Clear all the LSBs until this bit, then add largest number with one more bit count.

Following python script implement both solutions.

def bitCountSlow(num):
        count = 0
        while num != 0:
                num &= num - 1
                count += 1
        return count

g_bitCountFast = [0] * 256

def bitCountFastPrepare():
        global g_bitCountFast

        for i in range (0, 256):
                g_bitCountFast[i] = bitCountSlow(i)

def bitCountFast(num):
        global g_bitCountFast

        count = 0
        while num != 0:
                count += g_bitCountFast[num & 0xff]
                num >>= 8

        return count

def findNumWithSameBitsBrute(num, findLower):
        count_num = bitCountFast(num)
        while True:
                if findLower:
                        if num == 0:
                                return -1
                        num -= 1
                else:
                        num += 1

                if bitCountFast(num) == count_num:
                        return num

        return 0

def findNumWithSameBitsHigherFast(num):
        #
        # 0b01010000 => 0b01100000
        # 0b00100010 => 0b00100110
        # 0b01100000 => 0b10000001
        #
        # First first bit set from LSB
        # First next bit cleared
        # Set the bit : now one more bit is set
        # Clear the LSBs until this bit
        # Add lowest number with same bit count
        #

        bitmask = 1
        bitcount = 0
        while (num & bitmask) == 0:
                bitmask <<= 1
        while (num & bitmask) != 0:
                bitmask <<= 1
                bitcount += 1
        # add one bit
        num |= bitmask
        # remote one bit
        num &= ~(bitmask - 1)
        if bitcount > 1:
                num |= (1 << (bitcount - 1)) - 1

        return num

def findNumWithSameBitsLowerFast(num):
        #
        # 0b01010000 => 0b01001000
        # 0b00100010 => 0b00100001
        # 0b01100000 => 0b01010000
        #
        # First first bit clear from LSB
        # First next bit set
        # Clear the bit : now one less bit is set
        # Clear the LSBs until this bit
        # Add lowest number with same bit count
        #

        bitmask = 1
        bitcount = 0
        bitoffset = 0
        while (num & bitmask) != 0:
                bitmask <<= 1
                bitcount += 1
        while (num & bitmask) == 0:
                bitmask <<= 1
                bitoffset += 1
        # remove one bit
        num &= ~bitmask
        # add one bit
        num &= ~(bitmask - 1)
        num |= ((1 << (bitcount + 1)) - 1) << (bitoffset - 1)

        return num

Test program:

def intToBin32(num):
        bitmask = 1 << 31
        binStr = ""
        for i in range(0, 32):
                binStr += "0" if (num & bitmask == 0) else "1"
                bitmask >>= 1
                if i % 8 == 7:
                        binStr += " "
        return binStr

def findNumWithSameBitsTest(num):
        count_num = bitCountFast(num)

        result_lower_brute = findNumWithSameBitsBrute(num, True)
        count_lower = bitCountFast(result_lower_brute)
        result_higher_brute = findNumWithSameBitsBrute(num, False)
        count_higher = bitCountFast(result_higher_brute)
        print("{:x} : {} bits".format(num, count_num))
        print("  Lower/Brute {:x} : {} bits".format(result_lower_brute, count_lower))
        print("  Higher/Brute {:x} : {} bits".format(result_higher_brute, count_higher))

        result_lower_fast = findNumWithSameBitsLowerFast(num)
        count_lower = bitCountFast(result_lower_fast)
        result_higher_fast = findNumWithSameBitsHigherFast(num)
        count_higher = bitCountFast(result_higher_fast)
        print("  Lower/Fast {:x} : {} bits".format(result_lower_fast, count_lower))
        if result_lower_brute != result_lower_fast:
                print("  DO NOT MATCH")
        print("  Higher/Fast {:x} : {} bits".format(result_higher_fast, count_higher))
        if result_higher_brute != result_higher_fast:
                print("  DO NOT MATCH")
        print("  O: " + intToBin32(num))
        print("  L: " + intToBin32(result_lower_fast))
        print("  H: " + intToBin32(result_higher_fast))

def main():
        bitCountFastPrepare()
        findNumWithSameBitsTest(0x50)
        findNumWithSameBitsTest(0x22)
        findNumWithSameBitsTest(0x60)
        findNumWithSameBitsTest(0x1000)
        findNumWithSameBitsTest(0xaaaa)
        findNumWithSameBitsTest(0xc000)
        findNumWithSameBitsTest(0x0f33)
        findNumWithSameBitsTest(0x3673)

main()

Test result:

50 : 2 bits
  Lower/Brute 48 : 2 bits
  Higher/Brute 60 : 2 bits
  Lower/Fast 48 : 2 bits
  Higher/Fast 60 : 2 bits
  O: 00000000 00000000 00000000 01010000 
  L: 00000000 00000000 00000000 01001000 
  H: 00000000 00000000 00000000 01100000 
22 : 2 bits
  Lower/Brute 21 : 2 bits
  Higher/Brute 24 : 2 bits
  Lower/Fast 21 : 2 bits
  Higher/Fast 24 : 2 bits
  O: 00000000 00000000 00000000 00100010 
  L: 00000000 00000000 00000000 00100001 
  H: 00000000 00000000 00000000 00100100 
60 : 2 bits
  Lower/Brute 50 : 2 bits
  Higher/Brute 81 : 2 bits
  Lower/Fast 50 : 2 bits
  Higher/Fast 81 : 2 bits
  O: 00000000 00000000 00000000 01100000 
  L: 00000000 00000000 00000000 01010000 
  H: 00000000 00000000 00000000 10000001 
1000 : 1 bits
  Lower/Brute 800 : 1 bits
  Higher/Brute 2000 : 1 bits
  Lower/Fast 800 : 1 bits
  Higher/Fast 2000 : 1 bits
  O: 00000000 00000000 00010000 00000000 
  L: 00000000 00000000 00001000 00000000 
  H: 00000000 00000000 00100000 00000000 
aaaa : 8 bits
  Lower/Brute aaa9 : 8 bits
  Higher/Brute aaac : 8 bits
  Lower/Fast aaa9 : 8 bits
  Higher/Fast aaac : 8 bits
  O: 00000000 00000000 10101010 10101010 
  L: 00000000 00000000 10101010 10101001 
  H: 00000000 00000000 10101010 10101100 
c000 : 2 bits
  Lower/Brute a000 : 2 bits
  Higher/Brute 10001 : 2 bits
  Lower/Fast a000 : 2 bits
  Higher/Fast 10001 : 2 bits
  O: 00000000 00000000 11000000 00000000 
  L: 00000000 00000000 10100000 00000000 
  H: 00000000 00000001 00000000 00000001 
f33 : 8 bits
  Lower/Brute f2e : 8 bits
  Higher/Brute f35 : 8 bits
  Lower/Fast f2e : 8 bits
  Higher/Fast f35 : 8 bits
  O: 00000000 00000000 00001111 00110011 
  L: 00000000 00000000 00001111 00101110 
  H: 00000000 00000000 00001111 00110101 
3673 : 9 bits
  Lower/Brute 366e : 9 bits
  Higher/Brute 3675 : 9 bits
  Lower/Fast 366e : 9 bits
  Higher/Fast 3675 : 9 bits
  O: 00000000 00000000 00110110 01110011 
  L: 00000000 00000000 00110110 01101110 
  H: 00000000 00000000 00110110 01110101 
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox