Как найти наибольшую мощность на 2 меньше заданного числа

Ответ 1

Изменить res =(int)Math.pow(res, 2); к res *= 2; Это вернет следующую мощность 2 больше, чем res.
Окончательный результат, который вы ищете, будет, наконец, res/2 после окончания.

Чтобы код не переполнял пространство значений int, вы должны/могли изменить тип res на double/long, все, что может содержать более высокие значения, чем int. В конце концов вам придется бросать один раз.

Ответ 2

Integer.highestOneBit(n-1);

Для n <= 1 вопрос не имеет смысла. Что делать в этом диапазоне оставлено заинтересованному читателю.

Хорошая коллекция битовых алгоритмов переворота в Hacker Delight.

Ответ 3

Вы можете использовать этот бит взломать:

v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;
v >>= 1;

Ответ 4

Почему бы не использовать журналы?

public int largestPowerOf2(int n) {
    return (int)Math.pow(2, Math.floor(Math.log(n) / Math.log(2));
}

log(n)/log(2) сообщает вам, сколько раз 2 переходит в число. Получив слово, вы получите округление целочисленного значения.

Ответ 5

Там хорошая функция в Integer которая полезна, numberOfLeadingZeros.

С его помощью вы можете

0x80000000 >>> Integer.numberOfLeadingZeros(n - 1);

Что делает странные вещи, когда n равно 0 или 1, но для этих входов нет четко определенной "наивысшей мощности двух меньше, чем n ".

edit: этот ответ еще лучше

Ответ 6

Вы можете исключить младший значащий бит в n до тех пор, пока n не станет силой 2. Вы можете использовать побитовый оператор AND с n и n-1, который устранит младший значащий бит в n до тех пор, пока n не будет иметь силу 2. Если первоначально n было бы силой 2, тогда все, что вам нужно было бы сделать, это уменьшить n на 1.

public class MathPow{
   public int largestPowerOf2(int n){
      if((n & n-1) == 0){ //this checks if n is a power of 2
         n--; //Since n is a power of 2 we have to subtract 1
      }
      while((n & n-1) != 0){ //the while will keep on going until n is a power of 2, in which case n will only have 1 bit on which is the maximum power of 2 less than n. You could eliminate the != 0 but just for clarity I left it in
         n = n & n-1; //we will then perform the bitwise operation AND with n and n-1 to eliminate the least significant bit of n 
      }
      return n;
   }
}

ОБЪЯСНЕНИЕ:

Когда у вас есть число n (это не сила 2), наибольшая мощность 2, которая меньше n, всегда является самым значимым битом в n. В случае числа n, которое является степенью 2, наибольшая мощность 2 меньше n равна биту прямо перед единственным битом, который включен в n.

Например, если бы у нас было 8 (что равно 2 третьей степени), его двоичное представление равно 1 0 00, то 0, выделенное жирным шрифтом, будет наибольшей степенью 2 до n. Поскольку мы знаем, что каждая цифра в двоичном выражении представляет собой степень 2, то, если у нас есть число n, равное 2, наибольшая мощность 2 меньше n будет степенью 2 перед ней, что будет бит до единственного бит в n.

С числом n, которое не является степенью 2 и не равно 0, мы знаем, что в двоичном представлении n будет иметь разные биты, эти биты будут представлять собой сумму различных степеней 2, наиболее важная из которых быть самым значительным битом. Тогда мы могли бы вывести, что n - это только самый старший бит плюс некоторые другие биты. Так как n представлено в определенной длине битов, а самый старший бит - наивысшей степени 2, мы можем представить с таким количеством битов, но это также самое низкое число, которое мы можем представить с этим количеством бит, тогда мы можем заключить, что самый старший бит - наивысшая мощность 2 ниже n, потому что, если мы добавим еще один бит для представления следующей мощности 2, мы будем иметь мощность 2 больше n.

ПРИМЕРЫ:

Например, если бы у нас было 168 (что равно 10101000 в двоичном формате), то время займет 168 и вычитает 1, что составляет 167 (что равно 10100111 в двоичном формате). Тогда мы будем делать побитовое И на обоих числах. Пример:

  10101000
& 10100111
------------
  10100000

Теперь мы имеем двоичное число 10100000. Если мы вычитаем 1 из него, и мы используем побитовое И на обоих числах, получаем 10000000, что равно 128, что равно 2 на 7.

Пример:

  10100000
& 10011111
-------------
  10000000

Если n должно было первоначально иметь силу 2, то мы должны вычесть 1 из n. Например, если n равно 16, что равно 10000 в двоичном формате, мы бы вычитали 1, что оставило бы нас с 15, что равно 1111 в двоичном формате, и мы сохраняем его в n (что и есть). Затем мы переходим к while, который выполняет побитовый оператор AND с n и n-1, который будет равен 15 (в двоичном формате 1111) и 14 (в двоичном формате 1110).

Пример:

  1111
& 1110
--------
  1110

Теперь мы остаемся с 14. Затем выполняем побитовое И с n и n-1, которое равно 14 (двоичный 1110) и 13 (двоичный код 1101).

Пример:

  1110
& 1101
---------
  1100

Теперь у нас есть 12, и нам нужно только устранить один последний младший бит. Опять же, мы затем выполняем побитовое И на n и n-1, которое равно 12 (в двоичном 1100) и 11 (в двоичном формате 1011).

пример

  1100
& 1011
--------
  1000

Наконец, мы оставили 8, что является наибольшей степенью 2 меньше 16.

Ответ 7

Вы каждый раз возводите квадрат res, что означает, что вы вычисляете 2^2^2^2 вместо 2^k.
Измените оценку следующим образом:

int res = 2;
while (res * 2 < n) {
    res *= 2;
}

Обновить:

Конечно, вам нужно проверить переполнение int, в этом случае проверить

тогда как (res <= (n - 1)/2)

кажется намного лучше.

Ответ 8

public class MathPow
{
   public int largestPowerOf2 (int n)
   {
        int res = 2;        
        while (res < n) {
                res =res*2;
        }

        return res;
   }
}

Ответ 9

Вот рекурсивный метод смещения бит, который я написал для этой цели:

public static int nextPowDown(int x, int z) {
    if (x == 1)
        return z;
    return nextPowDown(x >> 1, z << 1);
} 

Или более короткое определение:

public static int nextPowTailRec(int x) {
    return x <= 2 ? x : nextPowTailRec(x >> 1) << 1;
}

Поэтому в вашем основном методе пусть аргумент z всегда равен 1. Параметры жалости по умолчанию здесь недоступны:

System.out.println(nextPowDown(60, 1));                // prints 32
System.out.println(nextPowDown(24412, 1));             // prints 16384
System.out.println(nextPowDown(Integer.MAX_VALUE, 1)); // prints 1073741824

Ответ 10

Найдите первый бит набора слева направо и сделайте все остальные биты 0s.

Если есть только 1 бит, то сдвиньте его налево.

Ответ 11

public class MathPow
{
   public int largestPowerOf2(int n)
   {
        int res = 1;        
        while (res <= (n-1)/2)
        {
            res = res * 2;
        }

        return res;
   }
}

Ответ 12

Если число является целым числом, вы всегда можете изменить его на двоичный, а затем узнать количество цифр.

n = (x>>>0).toString(2).length-1

Ответ 13

p=2;
while(p<=n)
{
    p=2*p;
}
p=p/2;

Ответ 14

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

найти длину данного числа в двоичном представлении. (13 в двоичном формате = 1101, длина 4)

затем сдвиг 2 на (4-2)//4 - длина заданного числа в двоичном

приведенный ниже код java решит это для BigIntegers (так в основном для всех номеров).

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        

    String num = br.readLine();
    BigInteger in = new BigInteger(num);
    String temp = in.toString(2);

    System.out.println(new BigInteger("2").shiftLeft(temp.length() - 2));

Ответ 15

Я увидел еще одно решение BigInteger выше, но это на самом деле довольно медленно. Более эффективным способом, если мы хотим выйти за пределы целого и длинного, является

BigInteger nvalue = TWO.pow(BigIntegerMath.log2(value, RoundingMode.FLOOR));

где TWO - просто BigInteger.valueOf(2L)

и BigIntegerMath взято из Гуавы.

Ответ 16

Я думаю, что это самый простой способ сделать это.

Integer.highestOneBit(n-1);

Ответ 17

Простые битовые операции должны работать

 public long largestPowerOf2 (long n)
 {      
 //check already power of two? if yes simply left shift
    if((num &(num-1))==0){
        return num>>1;
    }

  // assuming long can take 64 bits     
    for(int bits = 63; bits >= 0; bits--) {
        if((num & (1<<bits)) != 0){
            return (1<<bits);
        }
    }
    // unable to find any power of 2
    return 0;   
  }

Ответ 18

Немного поздно, но...

(Предполагая 32-битное число.)

n|=(n>>1);
n|=(n>>2);
n|=(n>>4);
n|=(n>>8);
n|=(n>>16);
n=n^(n>>1);

Объяснение:

Первый | убедитесь, что установлены исходный верхний бит и второй верхний бит. Второй | убедитесь, что эти два, а также следующие два и т.д., пока вы не нажмете все 32 бита. Т.е.

100010101 → 111111111

Затем мы удаляем все, кроме верхнего бита, посредством xor'ing строки из 1 с этой строкой из 1 сдвинутой влево, и мы получаем только один верхний бит, за которым следуют 0.

Ответ 19

/**
 * Find the number of bits for a given number. Let it be 'k'.
 * So the answer will be 2^k.
 */
public class Problem010 {

  public static void highestPowerOf2(int n) {
    System.out.print("The highest power of 2 less than or equal to " + n + " is ");
    int k = 0;
    while(n != 0) {
      n = n / 2;
      k++;
    }

    System.out.println(Math.pow(2, k - 1) + "\n");
  }

  public static void main(String[] args) {
    highestPowerOf2(10);
    highestPowerOf2(19);
    highestPowerOf2(32);
  }

}