C - Bitwise manipulation

Question

I'm very new to C and i'm trying to understand bitwise operators in C I found this code in front of me (to convert 2 to 37)

int main(void)
{
    int x = 2;
    x = (x<<x<<x) | (x<<x<<x) | (x << !!x) | !!x ;
    printf("%d\n" , x );  // prints 37 
}

Now it's the first time i see something like this (x<<x<<x) and i don't understand what it is doing. Can anyone please explain the second line in code in detail?

It's a bit-shift in the direction of the arrows. But goodness, this code is either too clever for me or it's really really obscure, no wonder you're struggling. Try writing the stuff out in binary and stepping through manually. e.g. 2<<1 is 4. Try running things one operation at a time with printf in between to get a good handle on it. — Pam, Aug 27 '18 at 09:40
I'm guessing it would just operate in the order it came in - the problem is it's two bit shifts one after the other. Mathematically, it's doing (x * (2^x))*2^x. Surely there's an easier way to write it? — Pam, Aug 27 '18 at 09:46
Just to make it clear: *Code given above is extremely poorly written*. You won't see in real life codebases, if they are written by true professionals. Good expressions are easily understandable. I don't understand why some tutorials/books/teachers throw this nonsense at beginners. — user694733, Aug 27 '18 at 09:49
Yeah - it's contrived homework code. Don't worry about it - nobody outside academia ever writes such code. You don't need to learn how it works. — Martin James, Aug 27 '18 at 09:55
@MartinJames: "You don't need to learn how it works." I think that is a good enough cause not to learn something. — phoxis, Aug 27 '18 at 10:02
This is obfuscated code and not suitable to **learn** about bitops. — too honest for this site, Aug 27 '18 at 12:06

Ilya · Answer 1 · 2018-08-27T10:32:56.883

9

I'd recommend you to split this long line into few small pieces (sometimes it is more effective to try such things; i.e. reading of the documentation only is not enough):

int x = 2;
printf("%d\n", x); // prints 2
printf("%d\n", x << x); // prints 8
printf("%d\n", x << x << x); // prints 32
printf("%d\n", !!x); // prints 1
printf("%d\n", x << !!x); // prints 4

printf("%d\n", x); // prints 2 (just to become sure that x was not changed)

So, you know that initial long line is equal to x = (32 | 32 | 1 | 4). But this is 32+4+1=37.

Let's see in details:

What is << and >>?

The shift operators bitwise shift the value on their left by the number of bits on their right:

<< shifts left and adds zeros at the right end.
>> shifts right and adds either 0s, if value is an unsigned type, or extends the top bit (to preserve the sign) if its a signed type.

Also the C standard says about E1 >> E2: "If E1 has a signed type and a negative value, the resulting value is implementation-defined." Arithmetic shift is not guaranteed.

Since << is left associative, x<<x<<x is evaluated as (x<<x)<<x.

See also: What are bitwise shift (bit-shift) operators and how do they work?

What is !!x?

It is an unary NOT and an unary NOT. !!x can be used as shorthand for (x != 0 ? 1 : 0).

edited Aug 27 '18 at 10:32

answered Aug 27 '18 at 09:44

Ilya

4,583
4
26
51

4

The C standard says about `E1 >> E2`: "*If `E1` has a signed type and a negative value, the resulting value is implementation-defined.*" Arithmetic shift is not guaranteed. – melpomene Aug 27 '18 at 09:50
@melpomene Thank you for this addition! – Ilya Aug 27 '18 at 09:52
6

I think it is also worth pointing out that because << is left associative, x< – dmuir Aug 27 '18 at 10:02
@dmuir Thank you! I extended the answer by these clarification. – Ilya Aug 27 '18 at 10:28
Actually there is no guarantee that !0 ("not 0") will be evaluated to 1. It can be any non-zero value – NoamD Aug 27 '18 at 11:10
2

@NoamD there is - [`!0 == 1`](https://stackoverflow.com/questions/7945950/is-logical-negation-of-zero-0-compiler-dependent-in-c) – Sander De Dycker Aug 27 '18 at 11:28
1

@NoamD Of course there is such a guarantee, C17 6.5.3.3 §5 "The result of the logical negation operator ! is 0 if the value of its operand compares unequal to 0, 1 if the value of its operand compares equal to 0." The standard can't get much clearer than that. – Lundin Aug 27 '18 at 11:34

score 5 · Accepted Answer · answered Aug 27 '18 at 11:32

This is known as "obfuscation": writing needlessly complex code in order to make something seem more advanced that it is.

Looking at the sub-expression x<<x<<x, it is simple logical left shifts. The operator associativity of shift operators is left-to-right, so the expression is equal to (x<<x)<<x.

We left shift 2 by 2 and get 8. 8 << 2, left shift 8 by 2 and get 32:

x = 32 | 32 | (x << !!x) | !!x ;

Then for any expression with bitwise OR 32 | 32 where the operands 32 are identical, is the very same thing as just writing 32 without the OR. So it is equivalent to:

x = 32 | (x << !!x) | !!x ;

!! is a somewhat common though obscure trick in C to convert any integer to a boolean value 0 or 1. !! is not one operator, but two times the logical not operator !. First we have !2 which is 0. Then !0 which gives 1. We are left with this:

x = 32 | (2 << 1) | 1;

2 << 1 is 4, so:

x = 32 | 4 | 1;

Write it in binary:

   0010 0000
OR 0000 0100
OR 0000 0001
------------
   0010 0101 = 0x25 hex = 37 dec

C - Bitwise manipulation

2 Answers2