What does this boolean "(number & 1) == 0" mean?

Question

On CodeReview I posted a working piece of code and asked for tips to improve it. One I got was to use a boolean method to check if an ArrayList had an even number of indices (which was required). This was the code that was suggested:

private static boolean isEven(int number)
{
    return (number & 1) == 0;
}

As I've already pestered that particular user for a lot of help, I've decided it's time I pestered the SO community! I don't really understand how this works. The method is called and takes the size of the ArrayList as a parameter (i.e. ArrayList has ten elements, number = 10).

I know a single & runs the comparison of both number and 1, but I got lost after that.

The way I read it, it is saying return true if number == 0 and 1 == 0. I know the first isn't true and the latter obviously doesn't make sense. Could anybody help me out?

Edit: I should probably add that the code does work, in case anyone is wondering.

Solution 1

Keep in mind that "&" is a bitwise operation. You are probably aware of this, but it's not totally clear to me based on the way you posed the question.

That being said, the theoretical idea is that you have some int, which can be expressed in bits by some series of 1s and 0s. For example:

...10110110

In binary, because it is base 2, whenever the bitwise version of the number ends in 0, it is even, and when it ends in 1 it is odd.

Therefore, doing a bitwise & with 1 for the above is:

...10110110 & ...00000001

Of course, this is 0, so you can say that the original input was even.

Alternatively, consider an odd number. For example, add 1 to what we had above. Then

...10110111 & ...00000001

Is equal to 1, and is therefore, not equal to zero. Voila.

Solution 2

You can determine the number either is even or odd by the last bit in its binary representation:

1 -> 00000000000000000000000000000001 (odd)
2 -> 00000000000000000000000000000010 (even)
3 -> 00000000000000000000000000000011 (odd)
4 -> 00000000000000000000000000000100 (even)
5 -> 00000000000000000000000000000101 (odd)
6 -> 00000000000000000000000000000110 (even)
7 -> 00000000000000000000000000000111 (odd)
8 -> 00000000000000000000000000001000 (even)

& between two integers is bitwise AND operator:

0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1

So, if (number & 1) == 0 is true, this means number is even.

---

Let's assume that number == 6, then:

6 -> 00000000000000000000000000000110 (even)

     &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&

1 -> 00000000000000000000000000000001

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

0 -> 00000000000000000000000000000000

and when number == 7:

7 -> 00000000000000000000000000000111 (odd)

     &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&

1 -> 00000000000000000000000000000001

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

1 -> 00000000000000000000000000000001

Solution 3

& is the bitwise AND operator. && is the logical AND operator

In binary, if the digits bit is set (i.e one), the number is odd.

In binary, if the digits bit is zero , the number is even.

(number & 1) is a bitwise AND test of the digits bit.

Another way to do this (and possibly less efficient but more understandable) is using the modulus operator %:

private static boolean isEven(int number)
{
    if (number < 0)
       throw new ArgumentOutOfRangeException();

    return (number % 2) == 0;
}

Solution 4

This expression means "the integer represents an even number".

Here is the reason why: the binary representation of decimal 1 is 00000000001. All odd numbers end in a 1 in binary (this is easy to verify: suppose the number's binary representation does not end in 1; then it's composed of non-zero powers of two, which is always an even number). When you do a binary AND with an odd number, the result is 1; when you do a binary AND with an even number, the result is 0.

This used to be the preferred method of deciding odd/even back at the time when optimizers were poor to nonexistent, and % operators required twenty times the number of cycles taken by an & operator. These days, if you do number % 2 == 0, the compiler is likely to generate code that executes as quickly as (number & 1) == 0 does.

Solution 5

Single & means bit-wise and operator not comparison

So this code checks if the first bit (least significant/most right) is set or not, which indicates if the number is odd or not; because all odd numbers will end with 1 in the least significant bit e.g. xxxxxxx1

View more solutions

Comments

[Andrew Martin]

@Eng.Fouad: What's infuriating is that I studied this early on at university and had forgotten all about it. Seems so obvious now!

[Andrew Martin]

Anybody know who linked this to that other post (which has nothing to do with this stuff)? Can I remove it somehow?

[cauon]

Damn this is actually really smart!

[Grijesh Chauhan]

it is faster then number % 2 to check if number is even by last bit

[Andrew Martin]

@cauon: My thoughts exactly. I could never have thought this up!

[Seng Cheong]

This was featured on Twitter.

[Andrew Martin]

@JonathonReinhart: What do you mean?

[Burhan Ali]

@AndrewMartin twitter.com/StackExchange/status/302768803719286785

[user207421]

You are misreading the expression. Take a look at where the parentheses are.

[Andrew Martin]

@EJP: Yeah, got it all sorted yesterday, thanks.

[contactmatt]

Although the code works, IMO, the fact that you had to post on SO asking about the code shows that the readability factor of it is lacking. Probably would have made sense to use the modulus operator (%) in this case, although I could be missing something.

[Vrushank]

@GrijeshChauhan Could you please elaborate as to how is this faster than number % 2 == 0 ??

[Grijesh Chauhan]

@Vrushank read this bitwise operations are substantially faster than division, several times faster than multiplication

[Andrew Martin]

I would have understood that you see. Honestly, the things I learn daily about Java. Never would have gotten that without people pointing it out.

[Aram Kocharyan]

I tend to use this exclusively. Clarity over performance in most cases.

[Andrew Martin]

I can't imagine it would be THAT much slower, if at all. Anybody got any information on this?

[Andrew Martin]

Thanks - your explanation makes it very clear. Plus any answer which ends in a Voila deserves an upvote.

[ratchet freak]

given that any half decent peephole optimizing compiler will see the %2 and translate to &1 also unless this is a proven bottle neck the runtime differences will be negligible

[Steve Kuo]

& is also logical AND. && short circuits while & does not.

[dan04]

number % 2 is not the same as number & 1 if number is negative.

[Mitch Wheat]

if you are being passed a negative length, then you have bigger problems! ;)

[Ryan Amos]

I'm curious if the Java compiler optimizes this away. @AndrewMartin It would be a lot slower. For &, you just iterate each bit and compare. % has to do more complex division.

[Alvin Wong]

Should probably also be aware of negative numbers in this answer.

[fluffy]

@RyanAmos "Iterate each bit?" Bitwise AND is a single operation in every CPU I've ever seen - it's among the easiest things to do in parallel.

[fluffy]

Also, I'd possibly amend this answer to include the factoid that n%k == n&(k-1) for all k which are a positive power of 2. It might not be what the asker asked but it's a handy thing to know.

[Alvin Wong]

@fluffy not saying that it wouldn't work, but not everyone knows two's complement.

[fluffy]

@MitchWheat There is no reason to throw on the number < 0 case - while an odd negative number mod 2 is -1, an even one mod 2 is still 0.

[Navin]

@fluffy shouldn't there be a log or 2^ somewhere in that expression?

[Navin]

Note that a single & can be used as a logical and if you want to keep side effects from expressions like f(x) & g(x)

[RiaD]

Why IllegalArgument on negative args? They may be even

[Andrew Martin]

I should have made clear that the method can ONLY accept positive numbers greater than 0 (there are catches for it in the runner class)

[sleske]

Note that strictly speaking using binary operators like & on signed ints is implementation-defined (because it depends on the interal representation of signed ints, which is implementation-defined). In practice, all modern C implementations use two's complement, so the point is moot. See stackoverflow.com/a/1161712/43681

[Andrew Martin]

@AlvinWong: For our assignment we are only dealing with positive numbers greater than 0. There are catches built into the runner main class to prevent any value less than or equal to 0 being accepted, so that's not an issue. Good point though!

[Konrad Rudolph]

If this is less efficient you should buy a new processor that does proper optimisations: even if the Java JIT doesn’t optimise this, the processor definitely should.

[fluffy]

@Navin Nope. You could also write it as (n%pow(2,k))==n&(pow(2,k)-1) or, a bit more efficiently, n%(1<<k)==n&((1<<k)-1)` but that's just a less-readable way of saying that the equivalence is for powers of 2.

[fluffy]

@AlvinWong And why do they have to know 2's complement?