-14

Find the highest power of two that divides x, a 64-bit integer, or return -1.
The zero case is not defined, since it dives any power of two, so your method can return any number.

I tried using the BigInteger.getLowestSetBit() for this, it returns the right answer but it's far from being optimal.

Example: Input -> output

  • 3 -> -1
  • 6 -> 1
  • 4256 -> 5
Improve this question
0

2 Answers 2

Reset to default
5

In the Long class, there is a handy static function numberOfTrailingZeros, which does almost what you want, except that it returns zero (instead of -1) when the input is not divisible by 2. You could handle that case in different ways. For example, extending the answer of @0x476f72616e

if ((num & 0x1) == 0) return Long.numberOfTrailingZeros(num); else return -1;
Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Same output as question. Good. --- -3 -> -1 Good. --- -4 -> 2 Good. --- 0 -> 64 Wrong!
@Andreas that's not specified in the question, and anyway there is no proper answer for zero because it is divisible by any power of two so there is no highest one
Whether the answer should be 0 or -1 is debatable, but 64 is certainly not the right answer. But I mostly put the comment here so people are aware of the issue, i.e. that negative numbers are handled (but should they be?), but zero is not (how should it be?), and that they should make their own decision on how those should be handled.
wow, java is definitely for lazy people :). JK of course, I learned from your answer.
@Andreas 0 is certainly not the right answer either, it's not any better than 64, 1 is for sure not the biggest power of two which zero is divisible by. It can't be -1 either, that would declare zero to be an odd number. There is nothing the answer should be, all options are wrong.
|
2

one algorithm may be: (pseudocode)

use a counter set to zero, put number in a var intvar do{

  1. shift right (integer divide by two) ->dividedvar
  2. if dividedvar*2 != intvar then dividedvar = 0 /exit condition/
  3. else (intvar = dividedvar and counter ++) } while dividedvar !=0

try it

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.