Kaleab_Asfaw's blog

What is proof for finding remainder(%) when n divide by k, if k is power of two.
By Kaleab_Asfaw, history, 6 years ago, In English

For any integer n and where k is power of 2,

n % k = n & (k-1)

Example

I wasn't able to proof this statement, how could it be proofed without taking number as example?

Thanks in Advance!

  • Vote: I like it
  • -19
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
6 years ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

Please see the definition of binary numbers.

→ Reply
  • »
    »
    6 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I think I know the definition of binary number (number in base 2), but I wasn't able to relate this the modulo operation.

    I am beginner here, can u help?

    → Reply
    • »
      »
      »
      6 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      You know (a+b)%m = a%m + b%m. Since you also know the definition of binary numbers, you can write it as a sum of some powers of 2 and you'll know why.

      → Reply
»
6 years ago, hide # |
← Rev. 2  
Vote: I like it +4 Vote: I do not like it

Say you want to find n%(2^x), note that in binary representation it denotes the last 'x' bits of 'n'(from LSB) because higher bits are powers of 2 with exponent >= x, next note that 2^x — 1 is just an 'x' bit number with all '1', so if you operate & between n and (2^x — 1), you'll get the last 'x' bits of 'n'(since higher bits become '0' and 1&y = y) which was the expected answer. Did you understand it?

→ Reply