Troubleshooting bitwise AND sequence of numbers, code provided
If you are given two integers A and B, where 0 <= A <= B <= 2 ^ 32. Find the bitwise AND integers in the range (A, B) inclusive. For example, A = 12 and B = 15,
12 and 13 and 14 and 15 = 12
My TA was not very helpful in explaining how to approach the problem and instead left everyone with a solution, when the business hours ended, now I can't get the solution out of my head, but I also don't understand the solution. In the code below, I've noticed lines that I understand and don't understand.
I tried using the pen and paper method for my own examples with small As and Bs, while I can visualize the code working, I cannot understand the theory why the code works.
private void run() {
Scanner in = new Scanner(System.in);
long a = in.nextLong();
long b = in.nextLong();
long diff = Math.max(((long) (Math.log(b - a) / Math.log(2)) - 1), 0);
//what does diff represent?
long shiftA = a >> diff; //right shift by diff okay
long shiftB = b >> diff; // " "
long result = shiftA;
for (long j = shiftA; j <= shiftB; j++) {
result = result & j; //don't understand the loop
}
result = result << diff; //left shift, but why?
System.out.println(result);
}
}
source to share
The part diff
is just optimization, which makes the code harder and harder (and possibly wrong in some cases) to save some execution time. (In general, this is a good idea only when performance matters and only with good benchmarks. Here we could easily spend more time understanding this optimization and solving it correctly than saving an unoptimized program several times).
Let's first discuss the main loop by setting diff = 0
. So a >> diff
== a
and result << diff
== result
, so we can ignore the whole thing.
The main loop implements the solution directly:
long result = a;
for (long j = a; j <= b; j++) {
result = result & j;
}
That is, bit and ( &
) each of the values together from the range [a .. b]. With a = 12 and b = 15 this is 12 & 13 & 14 & 15
. (In fact, if you carefully simulate it by hand, you will notice that it computes 12 & 12 & 13 & 14 & 15
, which gets the same result.) This is an important part to understand, basic looping and bitwise math.
The part diff
makes the code faster by choosing the least significant bit. For example. if some of the inputs are computed diff == 4
, then it a >> 4
shifts the 4 least significant bits a
, essentially a / 16
since 2 4 == 16. The loop will then execute 1 / 16th time. The code then shifts the result back, result << 4
by shifting 0 bits, essentially a * 16
.
diff
Note in the value that Math.log(b - a) / Math.log(2)
== log 2(b - a), which is the number of bits in b - a
. It works to calculate the number of least significant bits that will end in zero so that it can move them, loop over and over, and then shift the zeros at the end.
source to share
what does diff represent?
diff
uses a change to the base formula for logarithms to calculate the number of bits in the difference representation b-a
. If the difference takes K
bits to represent, then the last K-1
bits of the result of one of the numbers in the range [a..b]
will be set to zero, which means you can clear them in the result. Hence the left shift is on diff
at the end: it shifts the diff
zeros into the result.
I don't understand the cycle
The loop goes through the bit representations abbreviated 2 diff times, i.e. uses only the upper bits a
and b
. Since the lower bits diff
will be zero anyway, this solution computes 2 diffs instead of counting by 1
, reducing the time it takes to get the result.
Consider an example a=23
and b=39
. diff
equal 3
. Here are the representations with a comma separating the last 3 bits:
d b
-- -------
23 010,111
24 011,000
25 011,001
26 011,010
27 011,011
28 011,100
29 011,101
30 011,110
31 011,111
32 100,000 <<-- The last diff bits will be set to zero somewhere in the range
33 100,001
34 100,010
35 100,011
36 100,100
37 100,101
38 100,110
39 100,111
Since the last three bits are guaranteed to reach all zeros, the cycle can be counted by eight instead of one. This reduces the execution speed by eight times. Counting with an eight is done by shifting the number from the right by diff
first, then counting by one, and then shifting left by diff
.
source to share