24

I was reading this answer and it is mentioned that this code;

if (data[c] >= 128)
    sum += data[c];

can be replaced with this one;

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

I am having hard time grasping this. Can someone explain how bitwise operators achieve what if statement does?

Community
  • 1
  • 1
yasar
  • 13,158
  • 28
  • 95
  • 160

3 Answers3

30
if (data[c] >= 128)
    sum += data[c];

Clearly adds data[c] to sum if and only if data[c] is greater or equal than 128. It's easy to show that 

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

Is equivalent (when data only holds positive values, which it does):

data[c] - 128 is positive if and only if data[c] is greater or equal than 128. Shifted arithmetically right by 31, it becomes either all ones (if it was smaller than 128) or all zeros (if it was greater or equal to 128).

The second line then adds to sum either 0 & data[c] (so zero) in the case that data[c] < 128 or 0xFFFFFFFF & data[c] (so data[c]) in the case that data[c] >= 128.

harold
  • 61,398
  • 6
  • 86
  • 164
4

int t = (data[c] - 128) >> 31; sum += ~t & data[c];

(Note that this hack is not strictly equivalent to the original if-statement. But in this case, it's valid for all the input values of data[].)

(data[c] - 128) >> 31; //this is trying to extract only the sign bit of data[c] when data[c] is greater than or equal to 128, if it is less than 128 then (data[c] - 128) will automatically shift into some negative number thus setting the sign bit.

and sum += ~t & data[c]; will AND the value data[c] with either 1 or 0 depending upon the complemented value of sign bit.Signifies nothing will be added to sum if value((data[c] - 128)) is negative.

perilbrain
  • 7,961
  • 2
  • 27
  • 35
0
if (data[c] >= 128)
    sum += data[c];

is equal to 

if (data[c] - 128 >= 0)
    sum += data[c];

which means that add data[c] to sum if data[c] - 128 is not negative. So we need to extract sign of data[c] - 128. As data is 32bit int array. So for getting sign, we need to arithmetically shift it 32 - 1 = 31 times. So

int t = (data[c] - 128) >> 31; //where t is the sign of data[c] - 128, 0 for positive and 1 for negative
sum += ~t & data[c]; //Add data[c] in sum if t = 0 i.e when the sign of data[c] - 128 is positive
Abdul Rauf
  • 5,798
  • 5
  • 50
  • 70