2

I’m curious as to why the bitwise AND of any even number with 1 is equal to 0? I’ve looked at the binary representations of an odd number and 1, and have found that the following is always true for any odd number:

00101 (5)
00001 (1)
5 & 1 != 0

00100 (4)
00001 (1)
4 & 1 = 0

The least significant bit is always 1 for any odd number, and always 0 for any even number.

Why is this true? Does anyone have an explanation for this behavior?

7
  • 1
    This is how binary number (base 2 number system) works. It is just mathematics. The unit digit has weight pow(2,0), namely the weight of one (1), which is not divisible by 2. All higher digits have weights that are divisible by 2. You may find it helpful to think in terms of decimal number: numbers that are divisible by ten, say, fifty (50), have a zero in the digit place.
    – rwong
    Oct 14 '20 at 17:02
  • I'm curious about why the last digit of any number divisible by 10 is 0, why is that?
    – user253751
    Oct 15 '20 at 10:59
  • @user253751 because any number comprised of 10s (power) is divisible by 10 :D
    – p32094
    Oct 15 '20 at 13:31
  • @p32094 Does it also work in binary (where 10 means 2)?
    – user253751
    Oct 15 '20 at 14:46
  • @p32094 Yes, it also works in binary. It's just digits, a 0 in binary is the same as a 0 in decimal. Binary just has less digits to work with. You run out of digits earlier so you need to prefix the 1 sooner to count further. Oct 16 '20 at 6:11
7

First, looking at decimal

In base 10, we can easily determine the parity of an integer (whether it is even or odd), by looking at the parity of the last digit:

  • If a base 10 numbers ends in 0, 2, 4, 6, 8, we know it's even.
  • If it ends in 1, 3, 5, 7 or 9, we know it's odd.

This works because all higher powers of 10 (i.e. 10^n for n > 1) are all divisible by 2, since they're all divisible by 10 (and because 10 is divisible by 2). I.e. any number of hundreds, thousands, ten thousands, etc. are always even. It's the last digit that can introduce an indivisible portion to the number.

Relating back to binary

In base 2, it works much the same way. All higher powers of 2 are always even (2, 4, 8, ...). The parity is decided soley by the last bit:

  1. If it's 0, that means the binary has the form of something_divisible_by_2 + 0, which means it's still divisible by two, thus even.
  2. If it's 1, that means the binary has the form of something_divisible_by_2 + 1, which makes the whole integer no longer divisible by two, thus odd.

Relating back to your problem

From what we see above, we know that if you take an odd number, as you did, that means that its last bit is always 0.

When then have the integer 1, whose binary representation is 0...00001. Lets take all the bit positions except the last one, and call it the "tail".

The "tail" of the binary representation of 1 is all zeros. Since 0 & anything is always 0, we know that 1 & anything will always have a tail of all zeros.

The last bit's value is the AND of the last bit (least significant bit, LSB) of our odd number (which we saw will always be 0), with the last bit of 1, which is always 1.

0b10101010101010 (10,922) - Always has a `0` LSB
0b00000000000001 (     1) - Always has an all-zero tail, and a `1` LSB
---------------&----
0b00000000000000 (     0)
  └─────┬─────┘│
        │      └─ LSB is always `0` because of `0 AND 1` of LSBs
        └─ Tail is always zero because of the all-zero tail of `1`

Thus, the entire result is always only zeros.

2
  • Thank you for the clear explanation. I know some people think I'm an idiot for posting this question but I suppose I didn't understand the representation in binary.
    – p32094
    Oct 15 '20 at 13:29
  • Glad I could help :) Downvotes don't mean people think you're an idiot, it just reflects people desires on what they do and don't want to see on this site, with regards to what they hope to get out of it.
    – Alexander
    Oct 15 '20 at 14:10
4

To see why, let's start by finishing the AND operation and viewing the results in binary:

00101 (5)
00001 (1)
-----&
00001 (1)

00100 (4)
00001 (1)
-----&
00000 (0)

When we AND a variable (here 4 vs. 5) with a specific constant (here 1), we sometimes refer to the constant as a mask.  The mask here is 1 decimal, or in your example in 5 bits binary, is 00001.  The AND operation clears bits where the mask has 0's and keeps bits from the variable where the mask has 1's.  The only 1 bit in the mask is the least significant bit, so that bit value of the variable is transferred into the result, with all other bits cleared to zero.

The least significant bit in binary represents the ones position, and when the one's position is false, the number is even and when it is true, the number is odd.

2
  • Thanks for the comment. I should've phrased my question more clearly, I understand the bitwise operation, I was curious as to the mathematics behind it (mainly because I was overthinking it)
    – p32094
    Oct 15 '20 at 13:33
  • As to the math behind it, boolean algebra was developed hundreds of years ago, seen then as a simplified form of other mathematics (and=multiply, or=add, where the only inputs & outputs are all/true/1 & none/false/0) but they further realized that using only and/or/not you can do addition, subtraction, multiplication, etc..
    – Erik Eidt
    Oct 15 '20 at 14:32
2

I'm not sure whether I'm covering the same ground as the existing answers, but cast your mind back to learning Hundreds, Tens, and Units in primary school.

That system, in which there are ten different number symbols available to use (the Arabic numerals, 0 to 9), and each column (proceeding from right to left) is worth ten times the value as the column preceding, relates to the decimal system. So 125 (one hundred and twenty five) consists of 1 hundreds, 2 tens, and 5 units.

The binary system employs exactly the same principle, except that there are only two number symbols employed (0 and 1), and each column is merely worth twice the value as the column preceding.

So the first four columns in binary are 8, 4, 2, and 1 - eights, fours, twos, and units. And you can have either zero or one in each of these columns. 1000 in binary is equivalent to 8 in decimal, because there is a 1 in the 8s column.

Decimal 6 expressed in binary would be 110 - 1 in both the fours and the twos column. Decimal 4 would be binary 100 - a 1 in the fours column. Decimal 2 is binary 10 - a 1 in the twos column.

Now, it should be possible to see why an even number in binary, never has a 1 in the units column. Only odd numbers need to employ the units column, because all even numbers in binary are composed of one or more of the higher columns.

The equivalent principle in decimal would be the distinction between "round" and "non-round" numbers. A round number which is a multiple of 10, never needs to use the decimal units column, it always contains zero. Only non-round numbers, like 11, have anything other than a zero in the decimal units column. Evens are the "round" numbers of binary which don't use the units column, whilst odds are the "non-round" numbers which do use the units column.

So after that short walkthrough of binary numbers, you ask "why the bitwise AND of any even number with 1 is equal to 0?".

The answer is that the number 1, by definition (and in any number system), only employs a 1 in the units column. Any even number in binary, however, does not employ the units column, because any even number is "round" in binary.

So by ANDing 1 with an even number, you are ANDing a number which has just a single 1 in the units column, with another number which never has a 1 in the units column. The result of the AND operation must therefore always be 0 by definition, because no even number will ever have a 1 in the units column, and the number 1 will never have a 1 in any column other than the units column.

6
  • There's many ways to skin a cat, but this one is particularly similar to mine, even the lead-in is pretty much the same
    – Alexander
    Oct 14 '20 at 23:42
  • @Alexander-Reinstate-Monica, I can't deny the similarity as I acknowledged in my opening sentence, and I don't know whether I've done any better overall, but I did find the first half of your answer particularly difficult to parse, bearing in mind that the OP is obviously not a mathematician. Instead, I've tried to concentrate on reiterating the principles of the decimal positional number system (which I learned in school, and I assume others did), and then explaining binary in terms of a variation of the numerals available, the column weights, and the meaning of a "round" number.
    – Steve
    Oct 15 '20 at 11:14
  • In a case like that, I think it's better to edit existing answer than to "fork" them. "reiterating the principles of the decimal positional number system." That's probably a good thing, though given that OP is already using binary representations, I was assuming her got that much
    – Alexander
    Oct 15 '20 at 12:39
  • 1
    @Alexander-ReinstateMonica Without reading these comments, I just upvoted two answers: this one, and yours. I particularly like the mention of "round numbers" in this one, and the diagrams in yours; one might be more helpful to a reader than the other, depending on how visually they like to learn, so I think they complement each other well.
    – IMSoP
    Oct 15 '20 at 13:10
  • 1
    Both your answers helped to give me a better understanding so I appreciate it.
    – p32094
    Oct 15 '20 at 13:32
0

It is true, because an odd number's least significant bit is 1 and therefore you'll always end up getting a not zero number.

The second is true because even number's least significant bit is 0 and all other bits of 1 are zeros therefore the result must be zero.

0

Why is this true? Does anyone have an explanation for this behavior?

Number parity in binary

In any number in any base, the rightmost digit is always equal to the remainder when dividing a number by its base.

As a simple example, using base 10, pick a random number (no matter how big), divide by 10, and take the remainder. Every time, the rightmost digit of the number you picked is the same as the remainder.

61398643861898841835 % 10 = 5

I didn't need to calculate this. I just looked at the last digit of the number I randomly typed in, and knew conclusively that that was the remainder.

We divided by 10 in the above example because you picked a number in base 10. But since your question is about binary numbers, we're working in base 2, so we'd have to divide the number by 2.

The parity of a number (= it being even or odd) is essentially the same as asking if it can be divided by two without a remainder. Therefore, "does this number have a remainder when divided by two?" is the same as asking "is this number odd?"

The conclusion here is that when written in binary, the rightmost digit of a number is 0 when the number is even, and 1 when the number is odd.

Therefore, we can state that even numbers in binary always follow the pattern ???0, where ? represents an unknown value. We know that the last digit is a 0 because the number is even.

The number 1 in binary

Not much needs to be said here. The number one in binary is just 1, or, using our earlier number format, 0001.

AND logic

The AND table is fairly straightforward. The result is true only if both inputs are true.

Note that true is the same as 1, and false is the same as 0.

 A | B | Output
----------------
 0 | 0 | 0
 1 | 0 | 0
 0 | 1 | 0
 1 | 1 | 1

So let's try a thought experiment. Can you tell me the output if I don't tell you what B is? Since we don't know the value of B, I'll use ? to represent that unknown value.

Let's examine both options. Assume A is true:

1 AND ? = ...

You cannot actually know the outcome here. Depending on B being true or false, the output will change.

Let's assume A is false:

0 AND ? = ...

Here, you can actually be sure. It's impossible for AND to output true when any of its inputs is false. Since we know that at least one of them (A) is false, we can therefore state that the output is always going to be false, regardless of the value of the other input (B). No matter whether B is true or false, this is not going to change the output.

You can confirm this by looking at the table above. In all cases where A is 0, the output is also 0. There is not a single case where the output is 0

Binary number AND

When you & two binary numbers, what you're really doing is performing an AND operation between the respective digits.

If you take number ABCD and EFGH (where each letter represents a binary bit) and you & them together, the result will be a four digit number which we'll call IJKL. The value of these four digits will be:

I = A AND E
J = B AND F
K = C AND G
L = D AND H

Now let's go back to our two numbers.

  • The first number is an even number, so we know it's ???0
  • The second number is 1, so we know it's 0001

So what is the result of performing & on these numbers? Well, just like we did with the letters above, the result is going to be a 4 digit number (which I'll call MNOP), and we know how to calculate each of its digits:

M = ? AND 0
N = ? AND 0
O = ? AND 0
P = 0 AND 1

Remember what we concluded about AND logic: if any of the inputs is false/0, then we conclusively know that the output will also be false/0.

Even though we still have some unknown values in our above calculations, we can already see that every & calculation has at least one 0 in it. Therefore, we can conclude that every calculation's outcome is going to be 0.

This means that number MNOP will always be 0000, when one of the inputs was an even number, and the other input was equal to 1.

Not the answer you're looking for? Browse other questions tagged or ask your own question.