Короткая версия расчета

Question

У меня есть два метода, которые, я считаю, могут быть сделаны лучше, но не могут найти этот путь.

Первое:

public int calcPow(long num) { 
    int count = 0; 
    while(num/2!=0) { 
     num = num/2; 
     count++; 
    } 
    return count; 
} 

Второй:

private long findParentNumber(long value) { 
    for(int bitNum = 0; bitNum < Long.SIZE; bitNum++) { 
     if((value & (1L << bitNum)) != 0) { 
      return value^(1L << bitNum); 
     } 
    } 
    throw new RuntimeException("No parent number found"); 
} 

Я считаю, есть способы, чтобы сделать то же самое без петель. Вы можете помочь?

Cheers!

Answer 1

Для первого, вы можете использовать Math.log метод, который уже существует:

public static int log2(long number) { 
    return (int) Math.floor(Math.log(number)/Math.log(2)); 
} 

или это быстрее функции suggested by saka1029:

public static int log2(long number) { 
    return number == 0? 0: Long.numberOfTrailingZeros(Long.highestOneBit((number < 0)? number * -1: number)); 
} 

Как вы можете видеть, что я также изменил метод статического , поскольку я не вижу смысла использовать объект для получения журнала, когда объект не задействован. И во-вторых, я изменил имена на что-то более подходящее.

Для второго вы можете использовать побитовую проверку оператор &:

public static long removeSmallBit(long value) { 
    return value & (value - 1); 
} 

По существу вы удаляете наималейший бит из переменных и возвращаете этот номер после того как вы измените этот бит на 0. как вы можете видеть снова, я сделал метод статическим и изменил имя. 2-й ответ на этот вопрос вызван this answer submitted by harold

Answer 2

Для второго вы устанавливаете самый младший бит. Для этого достаточно хорошо известно, хотя и относительно потому, что кажется, что битаки вообще не известны.

Во всяком случае, это

return x & (x - 1); 

Логика здесь в том, что в x - 1, есть заимствуют работает через низшие нули, пока не достигнет самого низкого 1 бит, который он сбрасывает. Самые низкие нули оставлены, они затем удаляются с помощью ANDing с исходным номером.

Вы можете написать первую в терминах numberOfLeadingZeros, что было бы более корректно, чем взломы с плавающей запятой, которые всегда заставляют вас думать о том, насколько точны они могут быть (и в любом случае они медленны, выкл с петлей).

Редактировать: для полноты, которая была бы 63 - numberOfLeadingZeros(x), она отличается от вашего определения на x = 0, но это плохой вход в любом случае.

Answer 3

Попробуйте это для первого.

public int calcPow(long num) { 
    if (num == 0) return 0; 
    if (num < 0) num = -num; 
    return Long.numberOfTrailingZeros(Long.highestOneBit(num)); 
} 

Или это suggested by harold

public int calcPow(long num) { 
    return num == 0 ? 0 
     : 63 - Long.numberOfLeadingZeros(Math.abs(num)); 
}