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

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

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
  • Проголосовать: не нравится

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

Please see the definition of binary numbers.

→ Ответить
»
6 лет назад, скрыть # |
← 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?

→ Ответить