Блог пользователя Kaleab_Asfaw

What is proof for finding remainder(%) when n divide by k, if k is power of two.
Автор Kaleab_Asfaw, история, 4 года назад, По-английски

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!

  • Проголосовать: нравится
  • -19
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Please see the definition of binary numbers.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
»
4 года назад, # |
← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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?

→ Ответить