CODEWITHSUNDEEP
bitwise-operators
Sanjaykumar A
Sanjaykumar A

Reputation: 43

How to find remainder using bitwise operator?

Let's look at the following code.

int x = 5>>1;

What it does is, it divides the given value by 2 power of 1 (which is 2) and it returns the quotient. Is it possible to get remainder during bitwise operation?

Upvotes: 2

Views: 7723

Answers (2)

user2864740
user2864740

Reputation: 61975

A bitwise shift returns one value and thus "loses" any remainder.

For a power-of-two it can be paired with a bitmask that computes "what was lost" in the previously-applied shift.

int quotient = 5 >> 1;
int remainder = 5 & 0x01;

The mask value above can be computed with: ~((~(int)0) << 1); for a 32-bit int, ~0 == 0xFFFF, 0xFFFF << 1 == 0xFFFE and ~0xFFFE == 0x01.

So, replacing with variables:

int n = ..;
int z = ..;
int quotient = n >> z;
int remainder = n & ~((~(int)0) << z);

Likewise, in the more general case, integer division (/) is paired with the modulo operator (%). Each operator only returns one value.

int n = ..;
int z = ..;
int p = 1 << z;
int quotient = n / p;
int remainder = n % p;

Upvotes: 3

avicene
avicene

Reputation: 187

a % b is equivalent to (b - 1) & a

Upvotes: 2

Related Questions