Java Reference
In-Depth Information
Solution 64: The Mod Squad
The program initializes the
int
array
histogram
with one location for each of the mod 3 values (0,
1, and 2). All three locations are initially 0. Then the program loops the variable
i
over all 2
32
int
values, using the idiom introduced in
Puzzle 26
. Because the integer remainder operator (
%
) can
return a negative value if its first operand is negative, as discussed in
Puzzle 1
, the program takes
the absolute value of
i
before computing its remainder when divided by 3. Then it increments the
array location indexed by this remainder. After the loop finishes, the program prints the contents of
the
histogram
array, whose elements represent the number of
int
values whose mod 3 values are
0, 1, and 2.
The three numbers printed by the program should be roughly equal to one another, and they should
add up to 2
32
. If you want to know how to figure out their exact values and you're in the mood for a
bit of math, read the next two paragraphs. Otherwise, feel free to skip them.
The three numbers printed by the program can't be exactly equal, because they have to add up to
2
32
, which is not divisible by 3. If you look at the mod 3 values of successive powers of 2, you'll see
that they alternate between 1 and 2: 2
0
mod 3 is 1, 2
1
mod 3 is 2, 2
2
mod 3 is 1, 2
3
mod
3 is 2, and so
forth. The mod 3 value of every even power of 2 is 1, and the mod 3 value of every odd power of 2
is 2. Because 2
32
mod 3 is 1, one of the three numbers printed by the program will be one greater
than the other two, but which one?
The loop takes turns incrementing each of the three array values, so the last value incremented by
the loop must be the high one. This is the value representing the mod 3 value of
Integer.MAX_VALUE
or (2
31
- 1). Because 2
31
is an odd power of 2, its mod 3 value is 2, so (2
31
- 1)
mod 3 is 1. The second of the three numbers printed by the program represents the number of
int
values whose mod 3 value is 1, so we expect this value to be one more that the first and the last.
The program should therefore print floor(2
32
/ 3) ceil(2
32
/ 3) floor(2
32
/ 3), or
1431655765
1431655766 1431655765
— after running for a fair amount of time. But does it? No, it throws this
exception almost immediately:
Search WWH ::
Custom Search