CODEWITHSUNDEEP
ruby
mc9
mc9

Reputation: 6349

Bitwise AND as a modulo alternative

I would like to know why the following expressions produce the same result:

# method 1
def produce(n)
  n % 16
end

#method 2
def produce(n)
  n & 15
end

I understand that method 1 uses modulo operation, and that the method 2 uses 'bitwise AND'. But I am a little lost as to why calling & with 15 is the same as calling modulo 16.

I have a hunch that it only works for modulo x where x is 2^n. Any ideas?

Upvotes: 1

Views: 293

Answers (1)

Ben
Ben

Reputation: 9895

You are correct in thinking that this is to do with the modulo being 2^n. Lets take a look at how that breaks down in binary.

The first method with modulo 16 would look like this in binary:

10000

By comaparison to the bitwise and 15:

01111

In essence what you are doing with the modulo or remainder is getting what is left over when diving by 16. Since it is a power of 2 you are essentially removing all the bits above 16 since they divide evenly and leaving yourself with any bits below 16.

With the bitwise and you are also doing the same thing. You are keeping every bit below 16 and giving yourself the same result.

This will work for any number % 2^n and & (2^n - 1)

Upvotes: 3

Related Questions