0

For example in this answer to a reversing bits function problem made 4 years ago:

[reverse_Bits function] https://stackoverflow.com/a/50596723/19574301

Code:

def reverse_Bits(n, no_of_bits):
      result = 0
      for i in range(no_of_bits):
         result <<= 1
         result |= n & 1
         n >>= 1
      return result

I don't understand how to think the problem at all.

You multiply actual number (n) by one in order to check the first right side bit. Then you right shift this number by one so you are checking if the second bit is 0 when you and it again, and this for all bits. So basically you're adding 1 to the result if there is a 1 in the actual (?) bit. Aside you left shift the result so I understand you're trying to put the bit in its correct index and if there is a one you add it... I get lost here.

I mean, I know the code works and I know how but I couldn't do it from zero without having this reference because I don't know how you achieve thinking every step of the algorithm.

I don't know if I explain my problem or if it's just a mess but hoping somebody can help me!!

Ziark
  • 1

1 Answers1

0

If your question is, "how would I write this from scratch, without any help?" then I find personally that it comes about from a combination of sketching out simple cases, working through them manually, and progressive implementation.

For example, you may have started with example: You have the number 3 (because it is easy) and you want to reverse bits:

3 = 0000 0011 b 

need to &1 and if it is non-zero, write 1000 0000 b
need to &2 and if it is non-zero, write 0100 0000 b
need to &4 and as it is zero, write nothing... 
...

Okay, how can I automate 1,2,4,8,16,32 .. ? Can have a variable which will double, or I can left-shift a number by 1. Take your pick, does not matter.

For writing the values, same thing, how can I write 1000 0000 b and then 0100 0000 b, etc? Well start off as 1000 0000 b and divide by 2 or right-shift by 1.

With these two simple things, you will end up with something like this for one bit:

result = 0
src_mask = 0x01
dst_mask = 0x80 
if number & src_mask != 0:
    result |= dst_mask

One bit working. Then you add a loop so that you can do all bits and add a *2 for the src_mask and a /2 for the dst_mask as you do it to address each bit. Again this is all figured out from the scribbles on paper listing what I want to happen for each bit.

Then comes optimization, I don't like the 'if' so can I figure out a way of directly adding the bit without testing? if it was 0 it will add 0 and if the bit is set, then I add the bit?

This is generally the progression. Manual scribbles, first design and then step-by-step enhancements.

Chris
  • 2,655
  • 2
  • 18
  • 22