views:

345

answers:

4

Hi guys,

This is probably pretty basic... but I don't seem to get it:

How does

(2 & 1) = 0
(3 & 1) = 1
(4 & 1) = 0

etc..

This pattern above seems to help find even numbers

or

(0 | 1) = 1
(1 | 1) = 1
(2 | 1) = 3
(3 | 1) = 4
(4 | 1) = 5
(5 | 1) = 5

I know how boolean algebra works between bits. But I don't understand how Boolean algebra works with integers (in C# at the least).

thanks in advance.

+3  A: 

It works the same way in C# as it does in binary.

2 | 1 = 3 and 4 | 1 = 5.

To understand this, you need to think about the binary representation of 1,2,3,4,and 5:

010 | 001 = 011 and 100 | 001 = 101.

Similarly:

010 & 001 = 000 and 011 & 001 = 001

SoapBox
A: 

It is doing bitwise operations on the integer. That it is doing a logical or/and of each bit in the first integer with the corresponding bit in the other integer. It then returns the result of all of these operations. For example, 4 = 0100 and 1 = 0001, a logical and of these would and bit the bits in order and get 0000 (since 0&0 = 0, 1&0 = 0, 0&0 = 0, and 0&1 = 0). For or, you would get 0101 (since 0|0 = 0, 1|0 = 1, 0|0 = 0, and 0|1 = 1). The trick is that these are bitwise operations, not logical operations which operate only on boolean values in C#.

tvanfosson
+1  A: 

The key is that the CPU is doing 32 boolean operations in parallel, one for each bit position of the input integers (assuming 32 bit integers, of course).

Greg Hewgill
+2  A: 

You are getting the first result because you are performing a boolean and between the bit strings of the two numbers:

2 & 1 => 010 & 001 = 000 = 0
3 & 1 => 011 & 001 = 001 = 1
4 & 1 => 100 & 001 = 000 = 0
5 & 1 => 101 & 001 = 001 = 1

In effect, you are testing whether the '1' bit is set, which will only be true for odd numbers.

When performing or operations:

0 | 1 => 000 | 001 = 001 = 1
1 | 1 => 001 | 001 = 001 = 1
2 | 1 => 010 | 001 = 011 = 3
3 | 1 => 011 | 001 = 011 = 3
4 | 1 => 100 | 001 = 101 = 5
5 | 1 => 101 | 001 = 101 = 5

Since in this case the effect or the or is to always set the 1 bit, even numbers will be incremented by one to their nearest greater odd number.

chromakode