Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How is if-statement and bitwise operations same in this example?

Tags:

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?

like image 200
yasar Avatar asked Aug 19 '12 11:08

yasar


People also ask

What is use of bitwise operators Explain with examples?

Bitwise operations A bitwise operation operates on two-bit patterns of equal lengths by positionally matching their individual bits. For example, a logical AND (&) of each bit pair results in a 1 if both the first AND second bits are 1. If only one bit is a 1, the result is 0.

Which operation is used as bitwise and '?

Remarks. The bitwise AND operator ( & ) compares each bit of the first operand to the corresponding bit of the second operand. If both bits are 1, the corresponding result bit is set to 1. Otherwise, the corresponding result bit is set to 0.

Is bitwise or and addition same?

Addition and bit-wise or would be the same as bit-wise or would include any bits in either, and normal addition would do exactly the same given the mutually exclusive nature of your bits.


2 Answers

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.

like image 54
harold Avatar answered Sep 25 '22 16:09

harold


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.

like image 31
perilbrain Avatar answered Sep 26 '22 16:09

perilbrain