Updates from September, 2016 Toggle Comment Threads | Keyboard Shortcuts

  • loctv 1:35 pm on September 25, 2016 Permalink | Reply
    Tags: ,   

    Problem: Find the second rightmost bit in a number (1 line code) 

    Presented with the integer n, find the 0-based position of the second rightmost zero bit in its binary representation (it is guaranteed that such a bit exists), counting from right to left.

    Return the value of 2position_of_the_found_bit.

    Example

    For n = 37, the output should be
    secondRightmostZeroBit(n) = 8.

    3710 = 1001012. The second rightmost zero bit is at position 3 (0-based) from the right in the binary representation of n.
    Thus, the answer is 23 = 8.

    def secondRightmostZeroBit(n):
        return 2**(len(bin(n)[2:])-1-bin(n)[2:].rfind('0',0,len(bin(n)[2:])-(len(bin(n)[2:]) - bin(n)[2:].rfind('0')))) 
    

     

    Advertisements
     
    • Kevin Bui 11:42 am on October 11, 2016 Permalink | Reply

      There’s actually a way to do this with just pure bit-operations. First, n | (n+1) turns off the rightmost 0 bit (since we want to find the second rightmost). Then by negating that and AND’ing it with the number that’s +1 isolates the rightmost 0 bit:

      return (n | (n+1) + 1) & ~(n | (n+1))

      Example: (for 10110111 we want to get 01000000)

      n: 10110111
      n+1: 10111000
      n | (n+1): 10111111
      ~(n | (n+1): 01000000
      (n | (n+1) + 1: 11000000
      (n | (n+1) + 1) & ~(n | (n+1)): 01000000

    • loctv 10:20 am on October 12, 2016 Permalink | Reply

      Cool! I’m really bad at bit map manipulation, but I think this problem cant be solved with pure bit-operations like this, since the problem requires just one line of code and python does not have built-in flip bit operator.

    • Kevin Bui 11:29 am on October 12, 2016 Permalink | Reply

      Instead of the negate operator, you can substitue it with -n -1 since they’re equivalent, though more verbose 😦

    • loctv 11:46 am on October 12, 2016 Permalink | Reply

      Oops! my bad, it does have flip bit operator. Nice solution 🙂

  • loctv 1:15 pm on September 25, 2016 Permalink | Reply  

    Problem: Reverse the order of the bits in a given integer (1 line code) 

    Example

    • For a = 97, the output should be
      mirrorBits(a) = 67.

      97 equals to 1100001 in binary, which is 1000011 after mirroring, and that is67 in base 10.

    • For a = 8, the output should be
      mirrorBits(a) = 1.
    def mirrorBits(a):
        return int(''.join(list(bin(a)[2:])[::-1]), 2)
    

     

     
c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel