How does "&" work for numeric comparison?
&
is called the bitwise AND operator.
The operatorAND
beats the binary representation of the two supplied integers bit by bit. If the bits at the same position in both integers are 1, then the resulting integer will have a bit equal to 1. If not, the bit will be set to 0:
(a = 18).to_s(2) #=> "10010"
(b = 20).to_s(2) #=> "10100"
(a & b).to_s(2) #=> "10000"
if the number is already two, then one less will result in a binary number that only has the least significant bit. Using &
will do nothing.
- Example with 8:
0100 & (0100 - 1)
→(0100 & 0011)
→0000
To understand this, follow " How does this bitwise operation check cardinality of 2? "
Example via IRB:
>> 4.to_s(2)
=> "100"
>> 3.to_s(2)
=> "11"
>> 4 & 3
=> 0
>>
This is why you can say that 4
is the power of the 2nd number.
source to share
"&" bit "AND" (see http://calleerlandsson.com/2014/02/06/rubys-bitwise-operators/ ). It compares two numbers as described in the following example:
Suppose n = 4 (which is a power of two). This means n-1 = 3. In binary (which I write with ones and zeros in quotes like "1101011101" so we can see the bits), we have n = "100" and n-1 = "011" ...
The bitwise AND of these two numbers is 0 = "000" (in the next, each column contains only one 1, never two 1s)
100 <-- this is n, n=4
011 <-- this is n-1, n-1=3
---
000 <-- this is n & (n-1)
As another example, now let's say that n = 14 (not the strength of two) and therefore n-1 = 13. In this case n = "1110" and n-1 = "1101" and we have n and ( n-1) = 12
1110 <-- this is n, n=14
1101 <-- this is n-1, n-1=13
----
1100 <-- this is n & (n-1)
In the above example, the first two columns of n and n-1 contain 1, so the AND of those columns is one.
Okay, let's look at one last example where n is again a power of two (this should make it perfectly clear, if it isn't already, why is "poweroftwo?" Written as it is. Suppose n = 16 (which is a power of two).
Suppose n = 16 (which is a power of two). This means that n-1 = 15, so we have n = "10000" and n-1 = "01111".
The bitwise AND of these two numbers is 0 = "00000" (in the next, each column contains only one 1, never two 1s)
10000 <-- this is n, n=16
01111 <-- this is n-1, n-1=15
---
00000 <-- this is n & (n-1)
Warning. In the special case, when n = 0, the "power_of_two?" will return True, although n = 0 is not a power of two. This is because 0 is represented as a bit string of all zeros, and any ANDed value with a zero is zero.
So, generally speaking, the "power_of_two?" will return True if and only if n is a power of two or n is zero. The above examples only illustrate this fact, they do not prove it ... However, it is.
source to share
The procedure for decrementing one from a binary number begins with the least significant bit:
- if bit
0
- turn it to1
and go to next significant bit - if a bit
1
- turn it in0
and stop.
This means that if there is more than one digit in the number 1
, then not all digits will be switched (because you stopped before getting the most significant bit).
Let's say the first 1
in our number n
is in position i
. If we shift the right number n
, we get a portion of the number that didn't change when we decreased it, let's call it m
. If we shift the number n-1
, we should get the same number m
, precisely because this is the part that didn't change when we decreased it:
n >> i == m
(n - 1) >> i == m
Shifting the right two numbers by the same amount will also shift to the right by the same amount, the result &
is:
(n >> i) & ((n - 1) >> i) == 0 >> i
But 0 >> i
there is 0
, regardless of i
, therefore:
(n >> i) & ((n - 1) >> i) == 0
Let m
's put where we know it is:
m & m == 0
But we also know that:
m & m == m # for any m
So m == 0
!
Therefore, n & (n - 1) == 0
if and only if the column n
contains at most one 1
.
The only numbers that have at most one bit 1
are all (non-negative) cardinals 2
(the leading 1
and non-negative number of zeros after it), and the number 0
.
QED
source to share
We want to prove that
n & (n-1) == 0
if and only if n
is a degree 2
.
It can be considered that n
is a whole number more 1
. (In fact, I'll use this assumption to get the compression.)
If n
is a degree 2
, its binary representation is 1
at bit offset
p = log2(n)
and 0
all junior bit positions j
, j < p
. Moreover, since (n-1)+1 = n
, n-1
it should have 1
all the bit offset j
, 0 <= j < p
. Hence,
n & (n-1) == 0
It remains to prove that if is n
not a degree 2
and
n & m == 0
then m != n-1
. I assume that m = n-1
it will get squeezed, thus completing the proof.
n
is, of course, the most significant bit of 1. Since n
it is not a power of 2, n
has at least one other bit equal to 1
. Among these 1-bits, consider the one in the most significant bit position j
.
Since n & (n-1) == 0
, n-1
must have its binary representation 0
in position j
. When we add 1
in n-1
, to make it equal n
, it should be 1
offset j
, which means that n-1
should be 1
in all positions of bits j
. It also (n-1)+1
has zeros in all <bit positions j
after 1
. But since n = (n-1)+1
, this can only be true if j == 0
, since n & (n-1) == 0
. Therefore, for this to be true, the n
most significant and least significant bits, most of which are equal 1
, and all other bits must be zero. However, since n = (n-1)+1
this would mean n-1==0
and thereforen == 1
, a necessary contradiction.
(Wow! There should be easier proof!)
source to share
In the case of a power of two, it takes the binary form of one bit of the value 1, followed by zeros. Any such value when decrementing will have the form of a run of 1, so when using bitwise and, since it is necessarily less than the first, it will mask it. For example.
0b1000 and (0b1000 - 1) = 0b1000 and 0b111 = 0
So anything (num-1) can become, the key here is about the maximum bit of num, decreasing it we will clear it.
On the other hand, if the number is not two, the result must be nonzero.
The reason is that the operation can always be carried forward without touching the most significant bit, because there will always be a nonzero bit, and thus at least the most significant bit does it in a way to mask and show as a result.
source to share