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, 4 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?
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Please see the definition of binary numbers.

→ Reply
  • »
    »
    4 years ago, # ^ |
      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
    • »
      »
      »
      4 years ago, # ^ |
      ← 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
»
4 years ago, # |
← 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