Writing a bit flip algorithm

Question

I am trying to write an algorithm for the following problem.

Problem Statement.

You will be given a list of 32-bits unsigned integers. You are required to output the list of the unsigned integers you get by flipping bits in its binary representation (i.e. unset bits must be set, and set bits must be unset).

The code is as follows:

def bit_flip(a):
    return ~a & 0xffffffff

t = raw_input("")
a = map(int, t.split())
map(lambda x: x ^ 0xffffffff, a) 
for i in a:
    print bit_flip(int(i))

The input is

The output that i get is 4294967292

whereas the output is supposed to be

**2147483648
  4294967294
  4294967295**

I am not sure where I am wrong. The output is close to at least one line of the output, but not the same.

What is the input for that expected output? It seems you're flipping the bits twice (once with ^ and once in bit_flip) for each number. — Cameron
– Cameron, Commented Jan 15, 2015 at 17:17
yeah it is. I just finished a basic python class and i have been stuck on this problem for a while — sanster9292
– sanster9292, Commented Jan 15, 2015 at 17:23
I think in the last question, he was asking about the error he was getting. On this one, he's specifically asking about the algorithm/why his output is incorrect. — Feign
– Feign, Commented Jan 15, 2015 at 17:25

Cameron · Accepted Answer · 2015-01-15 17:37:04Z

Your output is correct. The 32-bit unsigned complement of 3 is indeed 4294967292. The full output produced by your program is:

which corresponds correctly to the numbers 3, 2147483647, 1, 0. You can more easily see this if you write them in hex:

Dec         Hex       ~Hex      ~Dec
3           3         FFFFFFFC  4294967292
2147483647  7FFFFFFF  80000000  2147483648
1           1         FFFFFFFE  4294967294
0           0         FFFFFFFF  4294967295

You seem to be flipping the bits twice, but throwing away the results the first time: map(lambda x: x ^ 0xffffffff, a) returns a list containing the flipped values, which you don't assign to anything. If you changed that line to assign the result back to a, you wouldn't need bit_flip anymore (which also flips the bits, just via a different method):

t = raw_input("")
a = map(int, t.split())
a = map(lambda x: x ^ 0xffffffff, a) 
for i in a:
    print i

Or even shorter:

for i in map(lambda x: int(x) ^ 0xffffffff, raw_input("").split()):
    print i

Mark Rogaski · Accepted Answer · 2015-01-15 17:34:05Z

0

The list returned by the map(lambda x: x ^ 0xffffffff, a) is the answer, but you're not using it.

At least it has the integers with the bits flipped, I'm not sure why the expected output has one fewer element than the input.

answered Jan 15, 2015 at 17:34

Mark Rogaski

1111 silver badge2 bronze badges

1 Comment

greybeard Over a year ago

(That might be due to the first number just telling how many proper test cases/inputs are to follow)

Collectives™ on Stack Overflow

Writing a bit flip algorithm

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related