Bit twiddling

[Francisco Gonzalez]

The following question is from K&B mock exam.

1. public class Bitwise2 {
2.   public static void main(String[] args) {
3.     int x =  ~10;
4.     int y = x ^ 12;
5.     System.out.println(y & 7);
6.    }
7.  }

I know how all those bitwise operators work. But I'm having a hard time to manually perform the calculations, and for the exam, time is an enemy.

What's the best approach to attack a question like that ?

Thanks,
Francisco

[Steven Bell]

First I would write out the three numbers in binary.
10 = 1010
12 = 1100
7 = 0111

Next ~1010 = 0101
So x = 0101
0101 ^ 1100 = 1001
So y = 1001
1001 & 0111 = 0001

So System.out.println(1);

I don't think there are any real tricks beyond that. From what I have heard there are only 1 or 2 of these questions on the test so taking a few minutes shouldn't be a problem (you only have to average 1 every 2 minutes).

[marc weber]

I sketch a table, with powers of 2 across the top and binary representations underneath...

...32  16   8   4   2   1  |
===========================|===========
                           |
... 0   0   1   0   1   0  |  10
                           |
... 1   1   0   1   0   1  | ~10 = x
                           |
... 0   0   1   1   0   0  |  12
                           |
... 1   1   1   0   0   1  | x ^ 12 = y
                           |
... 0   0   0   1   1   1  |   7
                           |
... 0   0   0   0   0   1  | y & 7 = 1

This is great practice, but it's unlikely that the actual exam will have bitwise questions this involved. Even so, time shouldn't be that much of a concern.

[Francisco Gonzalez]

Thanks Steven for your response.

But there is something I don't understand, ~10 is really:

1111 1111 1111 1111 1111 1111 1111 1010

So in your calculation you are discarding all the 1's at the begining, I don't think you can't do that, or you can ? I know you ended up with the right answer, but is that always going to work ?

Regards,
Francisco

[Jeff Jetton]

Originally posted by Francisco Gonzalez:
I know you ended up with the right answer, but is that always going to work ?

No, it won't always work. It did happen to work in this case, whether by luck or by clever foresight and optimization on the part of Steven.

The key is that final (y & 7) operation. "Anding" something by 7 effectively masks off all but the last three bits of the result, so even if you got bits 4 and up completely wrong, it wouldn't matter in this particular question.

- Jeff

[Steven Bell]

Originally posted by Francisco Gonzalez:
Thanks Steven for your response.

But there is something I don't understand, ~10 is really:

1111 1111 1111 1111 1111 1111 1111 1010

So in your calculation you are discarding all the 1's at the begining, I don't think you can't do that, or you can ? I know you ended up with the right answer, but is that always going to work ?

Regards,
Francisco

You're right, I saw the & 7 as a mask and ignored the higer bits (actually could have ignored the fourth one too). I should have said something as this only works with the mask there.

P.S. As a mental optimization you can generally keep track of the higher bits as a 0 or 1 as they are effected the same by most operations. Ned to be careful with that though and watch for right shifts.
[ April 13, 2005: Message edited by: Steven Bell ]