bitwise And C programming

Question

Can I please have some help understanding some bitwise and, and if shorthand? I put comments on what I thought it is.

//Bitwise AND not sure how it decides 32 or 0, then set board[i]    
board[i] = (randNum & 1024) ? 32 : 0;

//it the j variable j in the neighborOffset array, then mods it by 2048
//then takes that variable from the board array, then shifts 1 to 32
//then bitwise and of those 2 variables.
if(board[(i + neighborOffset[j]) % 2048] & (1 << 5))

//Not sure about this one. Can someone please explain it? 
board[i] |= ((board[i] ^ 34) && (board[i] ^ 35)) ? ( (board[i]^3) ? 0 : (1<<4)) : (1<<4);

//Not sure how it decides if it uses 'X' or ' '
putchar(board[i] ? 'X':' ');

-----------------------------------------------

I figured out this one.

    putchar(board[i] ? 'X':' ');

#include <stdio.h>
#include <unistd.h>
#include <time.h>
#include <signal.h>
#include <stdlib.h>
//#include <dos.h>


int main()
{
    int board[2048] = {0};
    board[0] = 5;
    board[1] = 9;
    board[2] = 0;
    board[3] = 2;

    putchar(board[0] ? 'X':' ');
    putchar(board[1] ? 'X':' ');
    putchar(board[2] ? 'X':' ');
    putchar(board[3] ? 'X':' ');
    printf(" \n");
    return (0);

}

Output

XX X

The reason on success putchar returns 1. http://www.cplusplus.com/reference/cstdio/putchar/

note that `x % 2048 == x & ((1<<11)-1) == x & 0x7ff` for positive `x`. — Niklas B., Apr 01 '14 at 16:39
Can you provide some additional information, such as the size of the board and what you think the code does? — GWW, Apr 01 '14 at 16:40
`(randNum & 1024)` -- 1024 is hex 400 or binary 1000000000. So that expression is checking the bit 10 from the right end to see if it's a one or a zero. — Hot Licks, Apr 01 '14 at 16:49
A common way to understand such horrible obsfucated code is to tear it apart and understand it's compoments (typically by using temporary variables) and then put it together again. — alk, Apr 01 '14 at 17:13
Also you might like to read here: http://en.wikipedia.org/wiki/Operators_in_C_and_C%2B%2B. Addtionaly all you need to know is that in C `0` is "false" and everything else is "true". — alk, Apr 01 '14 at 17:16
@cokedude: I don't understand the question "how do you know 1024 is hex?" Hex is just a convenient alternative way to write numbers; 1024 doesn't change its value when you write it in hex. This question gets asked a lot by beginners and it always confuses me; it's like asking whether the number 12 is different if you do math in French instead of English. Numbers are just numbers; we have different ways of writing them depending on what is convenient. — Eric Lippert, Apr 01 '14 at 18:22
@ Eric Lippert I didn't catch the 400 he wrote. Sorry. As we all know there is a huge difference between 1024 decimal and 1024 hex. — cokedude, Apr 01 '14 at 20:42
@alk thats really funny that you said its obsfucated code. The original author called it obsfucated.c :). — cokedude, Apr 01 '14 at 20:44

Eric Lippert · Answer 1 · 2014-04-01T20:56:27.520

Not sure about this one. Can someone please explain it?

board[i] |= ((board[i] ^ 34) && (board[i] ^ 35)) ? ( (board[i]^3) ? 0 : (1<<4)) : (1<<4);

Don't ask for a fish, ask how to catch fish. Instead of explaining this to you, let me teach you how to explain it to yourself.

I don't understand this crazy code any more than you do right now, so I'm going to write down the process that I would use to understand this code.

We begin to understand it by first reformatting it so that indentation gives us a clue:

board[i] |= 
    ((board[i] ^ 34) && (board[i] ^ 35)) ? 
        ((board[i]^3) ? 
            0 : 
            (1<<4)) : 
        (1<<4);

OK, that's not much better. Let's try to understand it by introducing two explanatory variables.

int original = board[i];
int result =  
    ((original ^ 34) && (original ^ 35)) ? 
        ((original ^ 3) ? 
            0 : 
            (1<<4)) : 
        (1<<4);
board[i] = original | result;

That's still not very clear. Let's try to undestand it by turning conditional expressions into conditional statements.

int original = board[i];
int result;
if ((original ^ 34) && (original ^ 35))
{
    if (original ^ 3)
        result = 0;
    else
        result = 1 << 4;
}
else
    result = 1 << 4;

board[i] = original | result;

Still not very clear, but now we can notice that the structure of the "if" statements is bizarre: we have two possible results, and in one of them all three conditions must be met, so why do we have nested if statements at all? Rewrite.

int original = board[i];
int result;
if ((original ^ 34) && (original ^ 35) && (original ^ 3))
    result = 0;
else
    result = 1 << 4;
board[i] = original | result;

OK, we're getting a lot simpler now. Let's think about those three conditions. What does

(original ^ 34) && ...

mean? Well, the condition will be considered to be true if and only if the result is not zero, so let's introduce three more explanatory variables and make that clear.

int original = board[i];
int result;
int condition34 = (original ^ 34) != 0;
int condition35 = (original ^ 35) != 0;
int condition3 = (original ^ 3) != 0;
if (condition34 && condition35 && condition3)
    result = 0;
else
    result = 1 << 4;
board[i] = original | result;

OK, now let's ask ourselves "what does (x ^ y) != 0 even mean? Under what circumstances can this be false? Only if x^y is zero. Under what circumstances can x^y being zero be true? Only if x and y have all the same bits. Under what circumstances can x and y have all bits the same? Only if they are equal. So the condition is false if and only if the operands are equal, and therefore it is true if and only if they are unequal. So we can rewrite this as:

int original = board[i];
int result;
int condition34 = (original != 34);
int condition35 = (original != 35);
int condition3 = (original != 3);
if (condition34 && condition35 && condition3)
    result = 0;
else
    result = 1 << 4;
board[i] = original | result;

Now we are getting somewhere. Now let's look at the action on board[i]. If result is zero then original|result is a no-op. The only other possibility is that result is 16. So let's rewrite this again, this time to eliminate result:

int original = board[i];
int condition34 = (original != 34);
int condition35 = (original != 35);
int condition3 = (original != 3);
if (condition34 && condition35 && condition3)
{ /* do nothing */ }
else
   board[i] = original | 16;

Now let's notice that we can invert the if and eliminate the "do nothing" case:

int original = board[i];
int condition34 = (original != 34);
int condition35 = (original != 35);
int condition3 = (original != 3);
if (!(condition34 && condition35 && condition3))
   board[i] = original | 16;

Now we can use the fact that

!(a && b)

is the same thing as

!a || !b

So:

int original = board[i];
int condition34 = (original != 34);
int condition35 = (original != 35);
int condition3 = (original != 3);
if ((!condition34) || (!condition35) || (!condition3))
   board[i] = original | 16;

But now we are inverting a not-equals, which seems silly. Turn them into equals and eliminate the inversion.

int original = board[i];
int condition34 = (original == 34);
int condition35 = (original == 35);
int condition3 = (original == 3);
if (condition34 || condition35 || condition3)
   board[i] = original | 16;

Now let's eliminate the explanatory variables again:

if ((board[i] == 34) || (board[i] == 35) || (board[i] == 3))
   board[i] |= 16;

And there you go. Now we have the program fragment in a form that can be understood. If the board position is 34, 35 or 3, then set the 16 bit, otherwise, do nothing.

I have no idea why someone would want to write the original program fragment when the way I've shown is so much more clear, but sometimes people write strange code.

This is what you do when you encounter code you can't make sense of: rewrite it into exactly equivalent code that you can make sense of. Simplifying complex expressions by extracting sub-expressions into explanatory variables is a great technique for that.

The persons code I am reading LOVES bitwise stuff and using as few lines of code as possible. — cokedude, Apr 01 '14 at 17:52
@cokedude: That's unfortunate. I note that my solution is actually *shorter* than the original solution in terms of non-whitespace characters, and has the benefits of being actually understandable by humans. Also, unless you're playing Code Golf, shorter programs are by no means better programs. — Eric Lippert, Apr 01 '14 at 18:19

score 0 · Answer 2 · edited May 23 '17 at 12:32

//Bitwise AND not sure how it decides 32 or 0, then set board[i]
board[i] = (randNum & 1024) ? 32 : 0;

The & operator is performing a bitwise AND operation

   xxxxxxxxxxx
 & 10000000000
 --------------
   ?0000000000

The ? will be 1 if the number had a 1 in the 1024 location and will be 0 other wise. Once this test is performed if the result was 1 then the anser 32 is returned, else 0 is returned. This if else conditional is performed using the ? ternary operator.

//Not sure how it decides if it uses 'X' or ' ' putchar(board[i] ? 'X':' ');

Here a similar test is being done with the ? ternary check. If the element at board[i] evaluates true then X else ' '

Take a look at my comments up top. I figured it out but it won't let me format it here. — cokedude, Apr 01 '14 at 20:32

bitwise And C programming

2 Answers2