-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
Ilya Gazman
  • 31,250
  • 24
  • 137
  • 216

2 Answers2

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;
harold
  • 61,398
  • 6
  • 86
  • 164
  • 1
    Same output as question. Good. --- `-3 -> -1` Good. --- `-4 -> 2` Good. --- `0 -> 64` *Wrong!* – Andreas Aug 24 '20 at 17:33
  • @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 – harold Aug 24 '20 at 17:34
  • 1
    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. – Andreas Aug 24 '20 at 17:38
  • wow, java is definitely for lazy people :). JK of course, I learned from your answer. –  Aug 24 '20 at 17:42
  • @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. – harold Aug 24 '20 at 17:43
  • @harold As I said, that is why I raised the issue, so people can be **aware**, and know that they might need to make a decision on *how* to handle edge cases like zero and negative numbers. – Andreas Aug 24 '20 at 17:53
  • Since the code cannot return 0 right now, I think that `0 -> 0` is a valid compromise, though technically it should be `1 -> 0`, `0 -> ?`. Given the changes to the question text, it's actually unclear if `1 -> 0` should be valid. – Andreas Aug 24 '20 at 17:56
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

gkab
  • 21
  • 4