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.

@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, Feb 16 '13 at 01:11
Anybody know who linked this to that other post (which has nothing to do with this stuff)? Can I remove it somehow? — Andrew Martin, Feb 16 '13 at 10:59
it is faster then `number % 2` to check if number is even by last bit — Grijesh Chauhan, Feb 16 '13 at 11:40
@cauon: My thoughts exactly. I could never have thought this up! — Andrew Martin, Feb 16 '13 at 12:09
@AndrewMartin https://twitter.com/StackExchange/status/302768803719286785 — Burhan Ali, Feb 16 '13 at 17:24
You are misreading the expression. Take a look at where the parentheses are. — user207421, Feb 17 '13 at 21:29
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. — contactmatt, Feb 19 '13 at 18:18
@GrijeshChauhan Could you please elaborate as to how is this faster than `number % 2 == 0` ?? — Vrushank, Feb 20 '13 at 02:55
@Vrushank read this [**bitwise operations are substantially faster than division, several times faster than multiplication**](http://en.wikipedia.org/wiki/Bitwise_operation) — Grijesh Chauhan, Feb 20 '13 at 06:04

score 119 · Accepted Answer · answered Feb 16 '13 at 00:49

119

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.

answered Feb 16 '13 at 00:49

Kirby

3,649
3
26
28

14

Thanks - your explanation makes it very clear. Plus any answer which ends in a Voila deserves an upvote. – Andrew Martin Feb 16 '13 at 01:05
1

Should probably also be aware of negative numbers in this answer. – Alvin Wong Feb 16 '13 at 05:04
3

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. – fluffy Feb 16 '13 at 07:07
1

@fluffy not saying that it wouldn't work, but not everyone knows two's complement. – Alvin Wong Feb 16 '13 at 07:07
1

@fluffy shouldn't there be a `log` or `2^` somewhere in that expression? – Navin Feb 16 '13 at 07:58
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 http://stackoverflow.com/a/1161712/43681 – sleske Feb 16 '13 at 10:34
@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! – Andrew Martin Feb 16 '13 at 12:08
@Navin Nope. You could also write it as `(n%pow(2,k))==n&(pow(2,k)-1)` or, a bit more efficiently, `n%(1< – fluffy Feb 17 '13 at 03:02
@AlvinWong And why do they have to know 2's complement? – fluffy Feb 17 '13 at 03:02

score 72 · Answer 2 · answered Feb 16 '13 at 01:08

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

Mitch Wheat · Answer 3 · 2013-02-16T02:13:18.323

18

& 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;
}

edited Feb 16 '13 at 02:13

answered Feb 16 '13 at 00:45

Mitch Wheat

295,962
43
465
541

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. – Andrew Martin Feb 16 '13 at 00:49
1

I tend to use this exclusively. Clarity over performance in most cases. – Aram Kocharyan Feb 16 '13 at 00:55
I can't imagine it would be THAT much slower, if at all. Anybody got any information on this? – Andrew Martin Feb 16 '13 at 00:59
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 – ratchet freak Feb 16 '13 at 01:45
2

`&` is also logical AND. `&&` short circuits while `&` does not. – Steve Kuo Feb 16 '13 at 01:55
5

`number % 2` is not the same as `number & 1` if `number` is negative. – dan04 Feb 16 '13 at 02:06
4

if you are being passed a negative length, then you have bigger problems! ;) – Mitch Wheat Feb 16 '13 at 02:16
1

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. – Ryan Amos Feb 16 '13 at 04:47
4

@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 Feb 16 '13 at 07:05
2

@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. – fluffy Feb 16 '13 at 07:08
Why IllegalArgument on negative args? They may be even – RiaD Feb 16 '13 at 08:54
1

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) – Andrew Martin Feb 16 '13 at 09:46
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. – Konrad Rudolph Feb 16 '13 at 13:42

score 9 · Answer 4 · edited Feb 20 '13 at 03:13

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.

iTech · Answer 5 · 2013-02-16T00:51:31.210

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

edited Feb 16 '13 at 00:51

answered Feb 16 '13 at 00:45

iTech

18,192
4
57
80

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)` – Navin Feb 16 '13 at 08:03

score 4 · Answer 6 · answered Feb 16 '13 at 00:53

& is a bitwise AND operation.

For number = 8:

The result is that (8 & 1) == 0. This is the case for all even numbers, since they are multiples of 2 and the first binary digit from the right is always 0. 1 has a binary value of 1 with leading 0s, so when we AND it with an even number we're left with 0.

score 3 · Answer 7 · answered Feb 16 '13 at 00:45

The & operator in Java is the bitwise-and operator. Basically, (number & 1) performs a bitwise-and between number and 1. The result is either 0 or 1, depending on whether it's even or odd. Then the result is compared with 0 to determine if it's even.

Here's a page describing bitwise operations.

Peter Karlsson · Answer 8 · 2013-02-16T00:54:48.133

3

It is performing a binary and against 1, which returns 0 if the least significant bit is not set

for your example

00001010 (10)

00000001 (1)

===========

00000000 (0)

edited Feb 16 '13 at 00:54

answered Feb 16 '13 at 00:49

Peter Karlsson

1,170
7
15

Naveen AH · Answer 9 · 2013-02-16T07:41:50.563

3

This is Logical design concept bitwise & (AND)operater.

return ( 2 & 1 ); means- convert the value to bitwise numbers and comapre the (AND) feature and returns the value.

Prefer this link http://www.roseindia.net/java/master-java/java-bitwise-and.shtml

edited Feb 16 '13 at 07:41

answered Feb 16 '13 at 07:34

Naveen AH

23
5

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

9 Answers9

Linked

Related