Reverse Bits - Binary - Leetcode 190 - Python

0:00 - Read the problem
1:15 - Drawing Explanation
7:13 - Coding Explanation

leetcode 190

#reverse #bits #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[thecuriousengineer]

Thanks for making this. TBH I found this one a bit difficult to follow (no pun intended).

Here's a simplified version –

res = 0

for i in range(32):

res = res << 1
bit = n%2
res += bit
n = n >> 1

return res

The algorithm in plain english –

1. Do the following 32 times (because we have 32 bit integer)
2. left shift res by 1
3. add n%2 to res
4. right shift n by 1

A simple example –

# Input: 1010

# res<<1 res+=n%2 n>>1
# 00 00 101
# 000 001 10
# 0010 0010 1
# 00100 00101 _

In my humble opinion, this solution is little bit hard to understand, especially people who just started to learn this kind of problems. Instead of that, it would better to understand if we generate result starting from end and shift left every time?

For example;

uint result = 0;

for(var i = 0; i < 32; i++)
{
result = result << 1;
if(n % 2 == 1)
{
result++;
}
n = n >> 1;
}

return result;

[iamsmitthakkar]

Agree with comments here. This video is not as simple as others. Here's a similar but simpler python solution with comments

def reverseBits(self, n: int) -> int:
res = 0

for i in range(32):
# shift left to make room for next bit
res = res << 1

# add the rightmost bit of n
res = res | (n & 1)

# shift the n to right to get the next bit
n = n >> 1

return res

[danny]

At first, i did a naive solution by creating an array of the reversed bits, then constructing a decimal number out of the array of bits, and returning that number. Surprising on leetcode, the runtime is more efficient than the other solutions.

def reverseBits(self, n: int) -> int:
bits = []

while n:
bits.append(n%2)
n = n >> 1

bits += [0] * (32-len(bits))

bits = bits[::-1]
res = 0
for idx, bit in enumerate(bits):
place_val = 2 ** (idx)
res += bit * place_val

return res

[mehmetnadi]

thanks for the explanation. i just dont like bit problems honestly.

[derickito]

Figured out the javascript solution. In order to force javascript to treat the result of shifting the bit to the left as an unsigned integer value you have to use >>> 0. So the final solution would look like this:

let result = 0

for (let i = 0; i < 32; i++) {
let bit = (n >>> i) & 1
result = (result | ((bit << (31 - i)) >>> 0)) >>> 0
}

return result

[erikm]

This is needlessly complicated, you dont need to use 31 - i, you can just shift <<1 each iteration

[metalalive]

If you are asked to explain the correctness of your code in this question, how can you do that in neat and concise way in a short time period (like 30 seconds) without talking about too much detail ? any feedback is appreciated

[jamesmandla]

res = 0
for i in range(32):
res = res << 1
res += n%2
n = n//2
return res

[rafael]

In Javascript, you have to make sure the result is unsigned with the following trick: res >>> 0.

var reverseBits = function (n) {
let res = 0;
for (let i = 0; i < 32; i++) {
const bit = (n >> i) & 1;
res |= bit << (31 - i);
}
return res >>> 0;
};

[techandmore]

res = 0
for i in range(31, -1, -1):
res += (n % 2) * (2 ** i)
n = n >> 1
return res

[elluck]

Sorry, but I find it hard to follow your explanation...

[dorondavid]

I'm guessing this is how you should be solving it, with bit operations, but for me, I would have just found the binary representation of the integer, converted it to string, read the string backwards, and then added the char to int value in the correct array position :D

[prabinlamsal]

So, if we want to shift the 1 value to the left and perform AND with n, we should do this line right? (but this one doesn't work, produces wrong result. Why might that be? )

bit = (1 << i) & n

[MichaelShingo]

You can get another O(1) solution (simpler to understand for me) by going through n from the first digit to the last, and multiplying it by the powers of 2 starting at 2^31

def reverseBits(self, n: int) -> int:
res = 0
for i in range(31, -1, -1):
if n % 2 == 1:
res += pow(2, i)
n >>= 1
return res

[Satwikakul]

at 9:49, you are shifting to the left, not the right. Just wanted to point out the mistake if people are confused.

[lil-mi-]

Very clear and helpful, thanks for sharing!

[cybernaut]

You can also write
"res |= (bit << (31 - i))"
instead of
"res = res | (bit << (31 - i))"
to further shorten the line.

[armand]

def reverseBits(self, n: int) -> int:
ans = 0

for _ in range(32):
ans <<= 1
if n & 1:
ans += 1

n >>=1

return ans

[nbs]

Thanks man! I was searching for this exact approach and I got it in the first search