CODEWITHSUNDEEP
javabit-manipulation
faisal abdulai
faisal abdulai

Reputation: 3819

java bit operators

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.

Upvotes: 3

Views: 220

Answers (4)

tomasb
tomasb

Reputation: 1673

>> 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

Upvotes: 0

assylias
assylias

Reputation: 328608

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?!

Upvotes: 1

Peter Lawrey
Peter Lawrey

Reputation: 533520

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

Upvotes: 1

Jon Skeet
Jon Skeet

Reputation: 1500555

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...)

Upvotes: 7

Related Questions