Logic Python task with bitwise operators

Question

I have a very specific task to complete and I am honestly lost in it. The goal is to define function in Python, that would remove all 1s in binary input that do not have any 1 next to it. I will show you in example.

Let's have input 0b11010 -–> the output of this would be 0b11000. Another example 0b10101 --> output would be Ob00000.

The real twist is that I cannot use any for/while loop, import any library or use zip, lists, map etc. The function needs to be defined purely using bitwise operations and nothing else.

I was already trying to implement the concepts of operations, but those were only blind shots and got nowhere. Any help would be appreciated, thanks!

kfx · Accepted Answer · 2022-11-30 09:43:45Z

To break down the condition mathematically, the i-th bit of the output should be 1 if and only if:

The i-th bit of the input is 1.
And either the (i-1)-th bit or the (i+1)-th bit of the input is also 1.

Logically the condition is input[i] and (input[i-1] or input[i+1]) if the input is a bit vector. If the input is simply a number, indexing can be emulated with bit shifting and masking, giving this code:

def remove_lonely_ones(b):
    return b & ((b << 1) | (b >> 1))

Testing shows that it works both on your examples and on edge cases:

print("{: 5b}".format(remove_lonely_ones(0b11111))) # prints 11111
print("{: 5b}".format(remove_lonely_ones(0b11010))) # prints 11000
print("{: 5b}".format(remove_lonely_ones(0b11011))) # prints 11011
print("{: 5b}".format(remove_lonely_ones(0b10101))) # prints 0
print("{: 5b}".format(remove_lonely_ones(0b00000))) # prints 0

Collectives™ on Stack Overflow

Logic Python task with bitwise operators

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related