donnemartin / donnemartin/interactive-coding-challenges

get_next_smallest method bug in get_next_challenge solution

Open
#298 0 comments 0 reactions 0 assignees View on GitHub
needs-review
Dominant language
Python
Stars
31.8k
Forks
4.7k
PR merge metrics
No merged PRs in 30d

Description

The get_next_smallest method in the solution for get_next_challenge is not implemented correctly. The problem is in the last line before the return:

```
# Clear all bits to the right of index
num &= ~((1 << index) - 1) <-- correctly clears the bits to right of index...
# Set bits starting from 0
num |= (1 << num_ones + 1) - 1 <-- but sets the bits 'right-aligned', when they should be 'left-aligned' up to the index of
the last zero before the non-trailing ones in the original number
```

E.g.

```
B = Bits()
num = 343434343
B.get_next_smallest(num)
```
Output:
`343434319`

The correct answer is 343434334

To illustrate what has went wrong:

343434343 is 10100011110000110010001100111 in binary.
343434319 is 10100011110000110010001001111 in binary.
343434334 is 10100011110000110010001011110 in binary.

So you can see that the incorrect answer is due to the 4 `1`s being added on the extreme right, rather than shifted up to the index of the last `0` before the non-trailing `1`s.

My solution that addresses this issue is:

```
def get_next_smallest(self, num):
if num is None:
raise TypeError('num cannot be None')
if num <= 0:
raise ValueError('num cannot be 0 or negative')

# handle numbers in which all bits are set - it is impossible to create a number less than
# this without using less set bits
if not (num + 1) & num:
return num

# create copy of num as we will need to shift it when counting 1s and 0s
num_copy = num
num_zeroes = 0
num_ones = 0

# count trailing 1s
while ((num_copy & 1) == 1):
num_ones += 1
num_copy >>= 1

# count number of 0s before first non-trailing 1
while (((num_copy & 1) == 0) and (num_copy != 0)):
num_zeroes += 1
num_copy >>= 1

# position of rightmost non-trailing one.
index = num_zeroes + num_ones

# clears from bit at index onwards
num &= ((~0) << (index + 1))

# Sequence of (num_ones + 1) ones
mask = (1 << (num_ones + 1)) - 1

# Shift the mask so the sequence of 1s is at the correct index, before applying it to num
num |= mask << (num_zeroes - 1)

return num

```

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.