CODEWITHSUNDEEP
c#linq
retlok
retlok

Reputation: 131

Group even and odd numbers

I'm learning about Linq and how you can group things and I was looking through my previous solutions and I found this:

public IList<IGrouping<int, int>> GroupEvenAndOddNumbers(int[] numbers)
{
    return numbers.ToLookup(x => x & 1).ToList();
}

This goes against the way I've been doing groupings, but I couldn't find a way to do it with the normal way. The problem is that I don't understand why this works, which shouldn't be a problem, but it would still be nice to know why this works. The part that I don't understand is the "x & 1" part. What logic is applied here?

Upvotes: 1

Views: 495

Answers (3)

Flater
Flater

Reputation: 13813

Parity (odd/even)

There is an interesting interaction between parity and binary numbers. All odd numbers end in 1, all even numbers end in 0.

Think of the decimal system, base 10. How do you know something is divisible by 10? Because it ends in a 0.
This works for every base. In base 8 (octal), numbers divisible by 8 end in a 0. In base 16 (hexadecimal), numbers divisible by 16 end in a 0. In base 12345, all numbers divisible by 12345 end in a 0. Pick any number, it always works.

And in base 2 (binary), numbers that are divisible by 2 (= even numbers, by definition) end in a 0.

AND

& is the bitwise AND operator. Very simply put, you pass it two binary values, and for each digit in the same place, it does a digitA AND digitB evaluation. The outcome is the value from these AND evaluations.

First of all, an AND evaluation only returns true when BOTH inputs are true. If at least one is false, the outcome is definitely also false.

Input A Input B Result
0 0 0
1 0 0
0 1 0
1 1 1

Now let's look at two random binary numbers, and for each digit position, figure out what the AND result would be.

         10110100
         10001011
 -[AND]------------
         10000000

Notice how only in the leftmost position, both bits are 1 (true), and therefore the result is also 1 (true). In all other positions, there is always a 0 (false) in one of the two input numbers, and therefore the outcome is 0 (false)

Let's now look at a special case. I'm going to hide the first number, and only show you the second number. Try to figure out how much of the result you can already guess.

         ????????
         00000001
 -[AND]------------
         ????????

Seems impossible, right? Well, let's think about it. In any position, if there is at least one 0, the result is definitely 0. Even though we don't know the first number, the second number already reveals that the first 7 digit positions will definitely result in a 0, because the second number already forces this by having 0s in those positions.

So now we know this:

         ????????
         00000001
 -[AND]------------
         0000000?

Let's think about that last digit. When will it be 1, when will it be 0? Think about this before reading the answer below.

If the first number ends on a 0, the result will also end on a 0, because 0 AND 1 = 0.
If the first number ends on a 1, the result will also end on a 1, because 1 AND 1 = 1

Remember what we said before? In binary, all odd numbers end in 1, all even numbers end in 0. So we could rewrite our earlier conclusion to say the following:

If the first number is even, the result will also end on a 0, because 0 AND 1 = 0.
If the first number is odd, the result will also end on a 1, because 1 AND 1 = 1

We can invert that logic:

If the result ends on a 0, then the first number is even.
If the result ends on a 1, then the first number is odd.

The code

numbers.ToLookup(x => x & 1).ToList()

ToLookup is essentially a group by statement. It groups all elements which have the same calculated value in the same group. These groups are being made based on the calculated value x & 1.

There are only two possible groups here. Using our demo values, the result is either 00000000 or 00000001 (because the first 7 digits are always 0, and the last digit could be different).

In the group labeled 00000000, you will find all numbers which ended on a 0, which is all even numbers.
In the group labeled 00000001, you will find all numbers which ended on a 1, which is all odd numbers.

The labels of the groups are of no importance. What is important here is that you've now correctly separated the evens and the odds.

There are other possible solutions here, but they all boil down to the same principle. One other example would be

var evenNumbers = numbers.Where(x => x % 2 == 0).ToList();
var oddNumbers  = numbers.Where(x => x % 2 == 1).ToList();

However, bit logic tends to be slightly more performant. This comes at the cost of bit logic being rather difficult, but in such a simple case as looking for number parity (even/odd), the performance gain is worth the minor complexity.

Upvotes: 5

mm8
mm8

Reputation: 169370

The & operator computes the logical AND of its operands and an odd number & 1 is always true (1) and an even number & 1 is always false (2).

So you're getting a lookup with two keys, 0 and 1, where the first groups contains all even numbers in numbers and the second group contains all odd numbers. It's as simple as that.

Upvotes: 0

palindrom
palindrom

Reputation: 19111

ToLookup groups numbers by the result of x & 1.

& is bitwise logical AND operator.

x & 1 equals to 0 when x is even and equals to 1 when it is odd. So ToLookup creates exactly 2 groups of elements: One with key 0 for even numbers, the other with key 1 for odd numbers.

Upvotes: 0

Related Questions