-1

I came across the below snippet for finding out the numbers in range[M,N] having odd divisors :

def printOddFactorNumber(n, m): 
      
    for i in range(n, m + 1): 
  
        # Check if the number is not a power of two 
        if ((i > 0) and ((i & (i - 1)) != 0)): 
            print(i, end = " ") 
              
N = 2
M = 10
  
printOddFactorNumber(N, M)

The logic is, the function prints all numbers which are not the power of 2. This found by performing & operation between the current number and the previous one. Can someone explain what does & mean between two integers? And the math behind how i&(i-1)!=0 means i is not power of 2 ?

anandhu
  • 686
  • 2
  • 13
  • 40
  • [`&` is bitwise AND](https://docs.python.org/3.4/reference/expressions.html#binary-bitwise-operations) – Nate Eldredge Jul 06 '20 at 15:25
  • Why `i` **is not** a power of 2, then both i and i-1 have the same high-order 1 bit in the same position. When ANDing i and i-1 the result will have a 1 in that position, which means it cannot be equal to zero. When `i` **is** a power of 2 it should be clear why i & (i-1) == 0. – President James K. Polk Jul 07 '20 at 17:03

2 Answers2

0

& is the bitwise and operation. When counting in binary a power of two has only one bit set, furthermore, one minus a power of two has all lower bits set to one except the bit for the power of two. &'ing them together will therefore give an overall zero for powers of two; (and only for i > 0 and i being a power of 2).

An example count:

INT  BIN   BIN-1 => i & (i-1)
  1  00001 00000 => 00000 << 2-power
  2  00010 00001 => 00000 << 2-power
  3  00011 00010 => 00010   
  4  00100 00011 => 00000 << 2-power
  5  00101 00100 => 00100   
  6  00110 00101 => 00100   
  7  00111 00110 => 00110   
  8  01000 00111 => 00000 << 2-power
  9  01001 01000 => 01000   
 10  01010 01001 => 01000   
 11  01011 01010 => 01010   
 12  01100 01011 => 01000   
 13  01101 01100 => 01100   
 14  01110 01101 => 01100   
 15  01111 01110 => 01110   
 16  10000 01111 => 00000 << 2-power
 17  10001 10000 => 10000   
 18  10010 10001 => 10000

Code (hack):

print("    INT  BIN   BIN-1 => i & (i-1)")
for i in range(1,19): 
    print(f"     {i:2}  {i:05b} {i-1:05b} => {i&(i-1):05b} {'  ' if i<=0 or i&(i-1) else '<< 2-power'}")
Paddy3118
  • 4,704
  • 27
  • 38
  • Hi @PresidentJamesK.Polk, I read your phrase "Same high-order bit position" as meaning that, for example in the above case for decimal 16 the 4th bit of 16 is a one but bits zero to three of decimal 15 are one. If you think of bit five or bit four as "the high-order bits" then they are **different**. – Paddy3118 Jul 07 '20 at 02:57
  • I was assuming that, as some things get shortened on SO - it would only work if that were the caseif you think about it - I assumed most would. I've added a further comment, and together with these comments... – Paddy3118 Jul 07 '20 at 16:16
-1

First of all, '&' is a bitwise AND operator

To understand it, let me go into a bit of binary using the examples 21, and 28

21 in binary is 10101, 28 in binary is 11100.

The '&' checks each corresponding bit in each of the numbers which is either a 1 or a 0, and if they both are 1, then it returns a 1, else it returns a 0. Like a simple AND logic gate.

so 21 & 28 would return 10100, which is 20.

More details:

def is_power_of_two(n):
    return (n != 0) and (n & (n-1) == 0)

As Python has arbitrary-precision integers, this works for any integer n as long as it fits into memory.

To summarize briefly the answer cited above: The first term, before the logical and operator, simply checks if n isn't 0 — and hence not a power of 2. The second term checks if it's a power of 2 by making sure that all bits after that bitwise & operation are 0. The bitwise operation is designed to be only True for powers of 2 — with one exception: if n (and thus all of its bits) were 0 to begin with.

To add to this: As the logical and "short-circuits" the evaluation of the two terms, it would be more efficient to reverse their order if, in a particular use case, it is less likely that a given n be 0 than it being a power of 2.

Anonymous
  • 528
  • 3
  • 17