Software Engineering Stack Exchange is a question and answer site for professionals, academics, and students working within the systems development life cycle. It only takes a minute to sign up.
Sign up to join this community
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?
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:
0, 2, 4, 6, 8, we know it's even.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.
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:
0, that means the binary has the form of something_divisible_by_2 + 0, which means it's still divisible by two, thus even.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.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.
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.
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.
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.
Why is this true? Does anyone have an explanation for this behavior?
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.
Not much needs to be said here. The number one in binary is just 1, or, using our earlier number format, 0001.
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
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.
???00001So 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.
