I came across this piece of code in java and will be delighted if someone can explain the logic to me.
public boolean name(int n) {
return ((n >> n) & 1L) > 0;
}
this is a kind of check operation I guess but what boolean value will this code return. And is there an alternative to this code. I am trying my best to understand bit manipulation in java.
That's a bizarre piece of code. It checks whether the number n, having been shifted right n % 32 bits, is odd.
The first non-negative values which pass are 37 (100101 in binary), 70 (1000110 in binary), and 101 (1100101 in binary).
I doubt that it actually works as the original coder intended it to - it doesn't obviously signify anything useful (and the method name of name is pretty unhelpful...)
32 >> 32 == 32
Perhaps the point of this puzzle was to see if you would consider shifting outside 0 to 31 bits and what would happen.
It gets more bizarre for negative numbers.
for(int n=-70;n<=200;n++)
if (((n >> n) & 1L) > 0)
System.out.print(n + " ");
prints
-70 -69 -68 -67 -66 -65 -58 -57 -56 -55 -54 -53 -52 -51 -50 -49 -48 -47 -46 -45 -44 -43 -42 -41 -40 -39 -38 -37 -36 -35 -34 -33 -27 -26 -25 -24 -23 -22 -21 -20 -19 -18 -17 -16 -15 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 37 70 101 102 135 165 167 198 199
A similar formula when n is an int
n & (1 << (n & 31)) != 0
if n was a long
n & (1L << (n & 63)) != 0
More negative numbers have a 1 set after shifting because they get sign extended.
A similar puzzle
http://vanillajava.blogspot.co.uk/2012/01/another-shifty-challenge.html
http://vanillajava.blogspot.co.uk/2012/01/shifting-challenge.html
For positive numbers, it seems that the function returns true iff a number is of the form:
sum_k (alpha_k * 2^k + d(k)), where
alpha_k = 0 or 1
k >= 5
d(k) = k for exactly one of the k where alpha_k = 1 and 0 otherwise
Example:
alpha_k = 1 for k = 5, 0 otherwise => 32 + 5 = 37
alpha_k = 1 for k = 6, 0 otherwise => 64 + 6 = 70
alpha_k = 1 for k = 5 and 6, 0 otherwise => 32 + 5 + 64 = 101
or 32 + 64 + 6 = 102
etc.
All those numbers will work:
shifting that number by itself % 32 shifts it by d(k) for the k that is not null.
the bit that goes to position 1 is in position k which is 1 by definition (alpha_k = 1)
Proving that only those numbers work is a bit more challenging...
Next question is obviously: what's the point?!
>> is signed right shift operator, left operand is integer to be shifted and the right one is the number of bit positions to shift the integer by. Final & 1L operation tests the zeroth bit: the function returns true if the zeroth bit is 1. True purpose of this is unknown to me, but the resulting set for which this function returns true is dependent on the operand size, e.g. for 32bit int the piece (n >> n) returns non-zero result for multiples of 32 and then ...
32: (n>>n): 32 (n>>n)&1L: 0
33: (n>>n): 16 (n>>n)&1L: 0
34: (n>>n): 8 (n>>n)&1L: 0
35: (n>>n): 4 (n>>n)&1L: 0
36: (n>>n): 2 (n>>n)&1L: 0
37: (n>>n): 1 (n>>n)&1L: 1
or
192: (n>>n): 192 (n>>n)&1L: 0
193: (n>>n): 96 (n>>n)&1L: 0
194: (n>>n): 48 (n>>n)&1L: 0
195: (n>>n): 24 (n>>n)&1L: 0
196: (n>>n): 12 (n>>n)&1L: 0
197: (n>>n): 6 (n>>n)&1L: 0
198: (n>>n): 3 (n>>n)&1L: 1
199: (n>>n): 1 (n>>n)&1L: 1
