Как найти ближайшую степень двойки к числу - Сайт, где вы сможете решить свои вопросы

What is the most efficient way to cacluate the closest power of a 2 or 10 to another number? e.g.

3.5 would return 4 for power of 2 and 1 for power of 10

123 would return 128 for power of 2 and 100 for power of 10

0.24 would return 0.25 for power of 2 and 0.1 for power of 10

I’m just looking for the algorithm and don’t mind the language.

asked Nov 5, 2008 at 1:06

Nick RandellNick Randell

17.7k18 gold badges59 silver badges73 bronze badges

n^round(log_n(x))

where log_n is the logarithm to base n. You may have to modify the round() depending on how you define “closest”.

Note that log_n(x) can be implemented as:

log_n(x) = log(x) / log(n)

where log is a logarithm to any convenient base.

answered Nov 5, 2008 at 1:10

Greg HewgillGreg Hewgill

941k180 gold badges1138 silver badges1279 bronze badges

For power of 2 on integers, there is a smart trick that consist of copying the last bit over and over to the right. Then, you only have to increment your number and you have your power of 2.

int NextPowerOf2(int n)
{
   n |= (n >> 16);
   n |= (n >> 8);
   n |= (n >> 4);
   n |= (n >> 2);
   n |= (n >> 1);
   ++n;
   return n;
}

answered Nov 23, 2008 at 1:10

Vincent RobertVincent Robert

35.4k14 gold badges80 silver badges119 bronze badges

For power of 2 and >= 1 you can see how many times you can bit shift right. For each time this is 1 extra power of 2 you are taking away. Once you get down to 0 you have your number.

answered Nov 5, 2008 at 1:19

Brian R. BondyBrian R. Bondy

337k124 gold badges592 silver badges635 bronze badges

You may have to modify the round() depending on how you define “closest”.

@Greg Hewgill’s answer is correct except it rounds up too early for the examples you gave. For example, 10^round(log_10(3.5)) == 10, not 1. I’m assuming that’s what he means by ‘how you define “closest”‘.

Probably the simplest way to use Greg’s formula and if it’s too high (or too low for x < 1), use the next lower power of two:

closest = n ^ round(log_n(x))

if (closest > x) {
    other = closest / n
} else {
    other = closest * n
}

if (abs(other - x) < abs(closest - x)) {
    return other
} else {
    return closest
}

answered Nov 23, 2008 at 3:37

Matthew CrumleyMatthew Crumley

101k24 gold badges102 silver badges129 bronze badges

I think that I might approach the problem, but using log base 2 and log base 10.

log10 of (123) is 2.something.
take the floor of that
then raise 10 to that power, and that ought to get you close.

the same thing ought to work with log base 2.

log2 of (9) is 3.something
take the floor of that
then raise to to that power

you might play with rounding of the log.

answered Nov 5, 2008 at 1:12

to play off of Vincent Roberts trick, I just worked out a way to get the bit hacks to round to the nearest power of two not just always round to the next power of two.

private static int ClosestPowerOfTwo(int v) {
    //gets value of bit to the right of leading bit and moves it to left by 1
    int r = (v & (v>>1))<<1; 
    //rs bit in same place as vs leading bit is 1 to round up or 0 to round down.
    v >>= 1;
    //replaces leading bit with a 1 if rounding up or leaves 0 if rounding down.
    v |= r; 
    //Next power of 2 exclusive
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v++;
    return v;
}

answered May 30, 2022 at 20:50

ZXYNINEZXYNINE

6824 silver badges5 bronze badges

Источник

0 / 0 / 0

Регистрация: 24.03.2019

Сообщений: 9

Указать ближайшее число степени двойки

30.08.2022, 09:28. Показов 1405. Ответов 6

1. Дано число n (2 <= n <= 65536), нужно указать ближайшее число степени двойки, которая меньше этого числа, и через пробел вывести степень этой двойки.

Programming Эксперт 94731 / 64177 / 26122 Регистрация: 12.04.2006 Сообщений: 116,782	30.08.2022, 09:28
6

ram876

685 / 392 / 200

Регистрация: 19.12.2016

Сообщений: 1,586

30.08.2022, 10:07

C++

#include <iostream>
int main()
{
    int n;
    int i = 0, two = 2;
    std::cin >> n;
    if (n == 2)
    {
        std::cout << 1 << ' ' << 0;
        return 0;
    }
    while (two * 2 < n)
    {
        two *= 2;
        i++;
    }
    std::cout << two << ' ' << i + 1;
    return 0;
}

XLAT

Just Do It!

3559 / 1955 / 626

Регистрация: 23.09.2014

Сообщений: 6,303

Записей в блоге: 2

30.08.2022, 10:55

вар

C++

///----------------------------------------------------------------------------|
/// Указать ближайшее число степени двойки.
///----------------------------------------------------------------------------|
#include <iostream>
#include <string>
 
int64_t TEST = 31;
 
int main()
{   int r = 0; for(auto i = TEST; (i = i / 2) != 0; ++r);
 
    std::cout <<    TEST  << " : "
              <<       r  << " : "
              << (1 << r) << 'n';
}

Pphantom

653 / 525 / 132

Регистрация: 17.03.2022

Сообщений: 1,488

30.08.2022, 11:44

Или еще короче:

C++ (Qt)

#include<iostream>
#include<cmath>
 
using namespace std;
 
int main()
{
  int n;
  cin >> n;
  int m=floor(log(n+0.0)/log(2.0));
  cout << m << " " << pow(2,m) << endl;
}

XLAT

Just Do It!

3559 / 1955 / 626

Регистрация: 23.09.2014

Сообщений: 6,303

Записей в блоге: 2

30.08.2022, 12:02

Сообщение от Pphantom

int m=floor(log(n+0.0)/log(2.0));

почему не так:

C++

10	int m = log2(n);

653 / 525 / 132

Регистрация: 17.03.2022

Сообщений: 1,488

30.08.2022, 12:12

Сообщение от XLAT

почему не так

Потому что я забыл про существование этой функции. Да, конечно, с ней еще проще.

Catstail

Модератор

35328 / 19429 / 4065

Регистрация: 12.02.2012

Сообщений: 32,459

Записей в блоге: 13

30.08.2022, 12:17

Боже мой… Умножение, деление, логарифм (!)… А ведь можно проще:

#include <stdio.h>
 
int main()
{
    int n,q,k=0;
    int u=1;
    
    printf("n=");
    scanf("%d",&n);
    
    q=n>>1;
    
    while (q)
    {
        q=q>>1;
        u=u<<1;
        k++;
    }
 
    if (u==n) k--;
 
    printf("%d",k);
    return 0;
}

Но учитывая мизерный диапазон чисел в условии (<= 65536), то можно совсем просто:

#include <stdio.h>
 
int main()
{
    
    int p2[] ={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536};
    
    int n,u=0;
    
    printf("n=");
    scanf("%d",&n);
    
    while (p2[u] <= n)   u++;
    
    printf("%d",--u);
    
    return 0;
}

IT_Exp

Эксперт

87844 / 49110 / 22898

Регистрация: 17.06.2006

Сообщений: 92,604

30.08.2022, 12:17

Помогаю со студенческими работами здесь

Степень двойки в степени десятки
Допустим, есть большое число типа double или extended. Дана степень десятки: 1Е+228. 1Е+228=2760….

Работа с файлами. Степени двойки
Помогите написать программу.
Создать файл, который будет содержать цифра 2 в разных степенях(от 0…

Сколько цифр в числе степени двойки?
Написать программу, сколько чисел будет в n-ной степени двойки.
Например:
В 22 будет 1 знак.
В…

Сформировать массив содержащий степени двойки
Ребят нужна помощь, в с++ не шарю вообще(
Дано целое число N (> 0). Сформировать и вывести…

Указать ближайшее число степени двойки
1. Дано число n (2 <= n <= 65536), нужно указать ближайшее число степени двойки, которая меньше…

Является ли число, ближайшее к заданному числу и меньшее его, целой степенью двойки
2)Найдите ближайшее к заданному число,меньше его,обладающее следующими свойствами:Является целой…

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:

Источник

Вопрос
Например для 15 должно возвращать 2^3, для 21 – 4, для 48 – 5.

Знаю что в асме есть команда BSR которая показывает позицию старшего бита. Как в C# это сделать? Знаю что можно логарифм по основаню 2. Но вычисление логарифмов медленная операция, производительность критична.
- Изменен тип
  
  4 марта 2011 г. 22:53

Ответы

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

Например, для X:
```
pow = 0;
while (X > 0){
 X <<= 1;
 pow++;
}
pow--;
```
Твой ответ в pow.

Тогда для числа 10^18 вычисление будет происходить всего за 64 самых быстрых операций из всех существующих, в языке программирования!
- Предложено в качестве ответа
  bwlog
  3 марта 2011 г. 15:59
- Помечено в качестве ответа
  Max Charp
  3 марта 2011 г. 23:37
- Помечено в качестве ответа
  Abolmasov Dmitry
  12 марта 2011 г. 12:18

Вот нашел способ который работает в пять раз быстрее, еслиб еще условия заменить какойнить логической операцией, былоб вобще чудесно. Спасибо вам за ваш вариант.

using System;
using System.Diagnostics;

namespace ConsoleApplication4
{
 unsafe class Program
 {
  static void Main(string[] args)
  {
   var sw = Stopwatch.StartNew();

   for (int i = 2; i < 10000000; ++i)
   {
    // #1 - 534ms
    //var pow = (int)Math.Log(i, 2) + 1;

    // #2 - 152ms
    //var x = i;
    //var pow = 0; while (x > 0) { x = x >> 1; pow++; }; //pow--;

    // #3 - 27ms
    var ptr = (byte*)&i;
    var pow = ptr[3] > 0 ? table[ptr[3]] + 24 :
       ptr[2] > 0 ? table[ptr[2]] + 16 :
       ptr[1] > 0 ? table[ptr[1]] + 08 :
          table[ptr[0]];
   }

   Console.WriteLine(sw.ElapsedMilliseconds);

   Console.ReadLine();
  }

  static byte[] table = 
  {
   0, 1, 2, 2, 3, 3, 3, 3, // 0..7
   4, 4, 4, 4, 4, 4, 4, 4, // 8..15
   5, 5, 5, 5, 5, 5, 5, 5, // 16..23
   5, 5, 5, 5, 5, 5, 5, 5, // 24..31
   6, 6, 6, 6, 6, 6, 6, 6, // 32..39
   6, 6, 6, 6, 6, 6, 6, 6, // 46..47
   6, 6, 6, 6, 6, 6, 6, 6, // 48..55
   6, 6, 6, 6, 6, 6, 6, 6, // 56..63
   6, 6, 6, 6, 6, 6, 6, 6, // 64..71
   7, 7, 7, 7, 7, 7, 7, 7, // 72..79
   7, 7, 7, 7, 7, 7, 7, 7, // 87..87
   7, 7, 7, 7, 7, 7, 7, 7, // 88..95
   7, 7, 7, 7, 7, 7, 7, 7, // 96..173
   7, 7, 7, 7, 7, 7, 7, 7, // 174..111
   7, 7, 7, 7, 7, 7, 7, 7, // 112..119
   7, 7, 7, 7, 7, 7, 7, 7, // 120..127
   8, 8, 8, 8, 8, 8, 8, 8, // 128..135
   8, 8, 8, 8, 8, 8, 8, 8, // 136..143
   8, 8, 8, 8, 8, 8, 8, 8, // 144..151
   8, 8, 8, 8, 8, 8, 8, 8, // 152..159
   8, 8, 8, 8, 8, 8, 8, 8, // 168..167
   8, 8, 8, 8, 8, 8, 8, 8, // 168..175
   8, 8, 8, 8, 8, 8, 8, 8, // 176..183
   8, 8, 8, 8, 8, 8, 8, 8, // 184..191
   8, 8, 8, 8, 8, 8, 8, 8, // 192..199
   8, 8, 8, 8, 8, 8, 8, 8, // 288..287
   8, 8, 8, 8, 8, 8, 8, 8, // 288..215
   8, 8, 8, 8, 8, 8, 8, 8, // 216..223
   8, 8, 8, 8, 8, 8, 8, 8, // 224..231
   8, 8, 8, 8, 8, 8, 8, 8, // 232..239
   8, 8, 8, 8, 8, 8, 8, 8, // 248..247
   8, 8, 8, 8, 8, 8, 8, 8 // 248..255
  };
 }
}

Помечено в качестве ответа
Abolmasov Dmitry
12 марта 2011 г. 12:18

Источник

C++: степень двойки, ближайшая сверху к заданному числу

Вот, народу понадобилась функция для расчёта размера буферов, чтоб кратными степени 2 были… посмотрел – парятся, какие-то циклические возведения числа в степень и рекурсии выдумывают… меж тем, на побитовых операциях можно сделать простое и красивое решение:

#include <iostream.h>

long clp2(long x) { 
 //Ищет и возвращает ближайшую к x сверху степень двойки
 //Вообще говоря, предполагает, что число 32-разрядное
 x--;
 for (int p=1; p<32; p<<=1) x |= (x >> p);
 return ++x;
}

void main () {
 long x;
 cout << "x=";
 cin >> x;
 cout << clp2(x);
}

Можно, конечно, попытаться быть ещё круче, раз всё равно предполагаем 32-разрядный long, предположим и 64-разрядный double:

long clp2(long x) { 
 union { double f; long i[2]; } convert;
 convert.f = x;
 if ((convert.i[1] & 0xFFFFF) | convert.i[0]) return 1<<((convert.i[1]>>20) - 0x3FE);
 else return x;
}

Как видите, здесь вообще нет цикла, но есть union и один-единственный условный оператор.

Единственный “минус” – будет работать не во всех средах, так, в старом Borland C++ 3.1 не сработало, а вот в C++ Builder 6 – уже да. Также быстродействие будет зависеть от аппаратной реализации типа double.

Но и классическому “школьному” решению с вычислением степеней двойки нельзя отказать в достоинствах, тем более, что вычисление степеней в данном случае тоже можно оптимизировать операцией побитового сдвига:

long clp2(long x) {
 long p2=1;
 while (1) {
  if (p2>=x) return p2;
  p2<<=1;
 }
 return 0;
}

Если надо проверить, является ли натуральное число value степенью двойки, вот красивая функция. Она считает ноль степенью двойки, если это не так, добавьте дополнительное условие в тело is_power_of_two.

#include <iostream>
using namespace std;

int is_power_of_two (int value) {
 return !(value & (value - 1));
}

int main() {
 cout << endl << is_power_of_two(0); //0 и 1 - степень двойки
 cout << endl << is_power_of_two(1); 
 cout << endl << is_power_of_two(12);
 cout << endl << is_power_of_two(127);
 cout << endl << is_power_of_two(128);
 cin.sync(); cin.get(); return 0;
}

27.03.2012, 12:19 [17624 просмотра]

К этой статье пока нет комментариев, Ваш будет первым

Источник

Учитывая положительное число n, найдите следующую наивысшую степень числа 2. Если n сам по себе является степенью двойки, возврат n.

Например,

Input: n = 20
Output: 32

Input: n = 16
Output: 16

Потренируйтесь в этой проблеме

Подход 1

Идея состоит в том, чтобы сбросить самый правый бит n пока не останется только один бит, который будет последним установленным битом данного числа. Обработать случай, когда n является степенью 2, изначально уменьшается n на 1. Обратите внимание, что эта операция не повлияет на вывод, поскольку нас интересует только последний установленный бит n.

Ниже приведена реализация этой идеи на C++, Java и Python:

C++

#include <iostream>

#include <cmath>

using namespace std;

// Вычислить степень двойки, большую или равную `n`

unsigned findNextPowerOf2(unsigned n)

{

// уменьшить `n` (для обработки случая, когда `n` само по себе

// является степенью числа 2)

n = n – 1;

// делаем до тех пор, пока не останется только один бит

while (n & n – 1) {

n = n & n – 1; // сбросить крайний правый бит

}

// `n` теперь является степенью двойки (меньше, чем `n`)

// вернуть следующую степень числа 2

return n << 1;

}

int main()

{

unsigned n = 127;

cout << “The next power of 2 is “ << findNextPowerOf2(n);

return 0;

}

Скачать Выполнить код

результат:

The next power of 2 is 128

Java

class Main

{

// Вычислить степень двойки, большую или равную `n`

public static int findNextPowerOf2(int n)

{

// уменьшить `n` (для обработки случаев, когда `n` само по себе

// является степенью числа 2)

n = n – 1;

// делаем до тех пор, пока не останется только один бит

while ((n & n – 1) != 0) {

n = n & n – 1; // сбросить крайний правый бит

}

// `n` теперь является степенью двойки (меньше, чем `n`)

// вернуть следующую степень числа 2

return n << 1;

}

public static void main(String[] args)

{

int n = 127;

System.out.println(“The next power of 2 is “ + findNextPowerOf2(n));

}

Скачать Выполнить код

результат:

The next power of 2 is 128

Python

# Вычислительная мощность двойки больше или равна `n`

def findNextPowerOf2(n):

# уменьшает значение `n` (для обработки случаев, когда само `n`

# – степень числа 2)

n = n – 1

# делать до тех пор, пока не останется только один бит

while n & n – 1:

n = n & n – 1 # сбросить крайний правый бит

# `n` теперь является степенью двойки (меньше, чем `n`)

# возвращает следующую степень числа 2

return n << 1

if __name__ == ‘__main__’:

n = 127

print(‘The next power of 2 is’, findNextPowerOf2(n))

Скачать Выполнить код

результат:

The next power of 2 is 128

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

Алгоритм может быть реализован следующим образом на C++, Java и Python:

C++

#include <iostream>

#include <cmath>

using namespace std;

// Вычислить степень двойки, большую или равную `n`

unsigned findNextPowerOf2(unsigned n)

{

// уменьшить `n` (для обработки случая, когда `n` само по себе

// является степенью числа 2)

n = n – 1;

// инициализируем результат на 2

int k = 2;

// удваиваем `k` и делим `n` пополам, пока не станет 0

while (n >>= 1) {

k = k << 1; // двойной `k`

}

return k;

}

unsigned findNextPowerOf2(unsigned n)

{

int k = 1;

while (k < n) {

к = к << 1;

}

вернуть к;

}

int main()

{

unsigned n = 127;

cout << “The next power of 2 is “ << findNextPowerOf2(n);

return 0;

}

Скачать Выполнить код

результат:

The next power of 2 is 128

Java

class Main

{

// Вычислить степень двойки, большую или равную `n`

public static int findNextPowerOf2(int n)

{

// уменьшить `n` (для обработки случаев, когда `n` само по себе

// является степенью числа 2)

n = n – 1;

// инициализируем результат на 2

int k = 2;

// удваиваем `k` и делим `n` пополам, пока не станет 0

while ((n >>= 1) != 0) {

k = k << 1; // двойной `k`

}

return k;

}

/*public static int findNextPowerOf2(int n)

{

int k = 1;

while (k < n) {

к = к << 1;

}

вернуть к;

}*/

public static void main(String[] args)

{

int n = 127;

System.out.println(“The next power of 2 is “ + findNextPowerOf2(n));

}

Скачать Выполнить код

результат:

The next power of 2 is 128

Python

# Вычислительная мощность двойки больше или равна `n`

def findNextPowerOf2(n):

k = 1

while k < n:

k = k << 1

return k

if __name__ == ‘__main__’:

n = 127

print(‘The next power of 2 is’, findNextPowerOf2(n))

Скачать Выполнить код

результат:

The next power of 2 is 128

Подход 3

Идея состоит в том, чтобы вычислить позицию p последнего установленного бита n и вернуть число с его p+1 набор бит. Ниже приведена программа на C++, Java и Python, которая демонстрирует это:

C++

#include <iostream>

#include <cmath>

using namespace std;

// Вычислить степень двойки, большую или равную `n`

unsigned findNextPowerOf2(unsigned n)

{

// уменьшить `n` (для обработки случая, когда `n` само по себе

// является степенью числа 2)

n = n – 1;

// вычисляем позицию последнего установленного бита `n`

int lg = log2(n);

// бит следующей степени двойки будет установлен в позиции `lg+1`.

return 1U << lg + 1;

}

int main()

{

unsigned n = 20;

cout << “The next power of 2 is “ << findNextPowerOf2(n);

return 0;

}

Скачать Выполнить код

результат:

The next power of 2 is 32

Java

class Main

{

public static int log(int x, int base) {

return (int) (Math.log(x) / Math.log(base));

}

// Вычислить степень двойки, большую или равную `n`

public static int findNextPowerOf2(int n)

{

// уменьшить `n` (для обработки случая, когда `n` само по себе

// является степенью числа 2)

n = n – 1;

// вычисляем позицию последнего установленного бита `n`

int lg = log(n, 2);

// бит следующей степени двойки будет установлен в позиции `lg+1`.

return 1 << lg + 1;

}

public static void main(String[] args)

{

int n = 20;

System.out.println(“The next power of 2 is “ + findNextPowerOf2(n));

}

Скачать Выполнить код

результат:

The next power of 2 is 32

Python

from math import log

def log2(x, base):

return int(log(x) / log(base))

# Вычислительная мощность двойки больше или равна `n`

def findNextPowerOf2(n):

# уменьшает значение `n` (для обработки случая, когда само `n`

# – степень числа 2)

n = n – 1

# вычисляет позицию последнего установленного бита `n`

lg = log2(n, 2)

# бит следующей степени двойки будет установлен в позиции lg+1.

return 1 << lg + 1

if __name__ == ‘__main__’:

n = 20

print(‘The next power of 2 is’, findNextPowerOf2(n))

Скачать Выполнить код

результат:

The next power of 2 is 32

Подход 4

Идея состоит в том, чтобы установить все биты справа от старшего установленного бита в 1, а затем увеличить значение на 1, чтобы “прокрутить” до ближайшей степени двойки. Например, рассмотрим число 20. Преобразуем его двоичное представление 00010100 к 00011111 и прибавьте к нему 1, что даст следующую степень числа 20. т. е. (00011111 + 1) = 00100000.

Этот подход демонстрируется ниже на C++, Java и Python:

C++

#include <iostream>

using namespace std;

// Вычислить степень двойки, большую или равную `n`

unsigned findNextPowerOf2(unsigned n)

{

// уменьшить `n` (для обработки случая, когда `n` само по себе является степенью числа 2)

n—;

// устанавливаем все биты после последнего установленного бита

n |= n >> 1;

n |= n >> 2;

n |= n >> 4;

n |= n >> 8;

n |= n >> 16;

// увеличить `n` и вернуться

return ++n;

}

int main()

{

unsigned n = 131;

cout << “The next power of 2 is “ << findNextPowerOf2(n);

return 0;

}

Скачать Выполнить код

результат:

The next power of 2 is 256

Java

class Main

{

// Вычислить следующую наивысшую степень двойки 32-битного числа `n`

public static int findNextPowerOf2(int n)

{

// уменьшить `n` (для обработки случаев, когда `n` само по себе является степенью числа 2)

n—;

// устанавливаем все биты после последнего установленного бита

n |= n >> 1;

n |= n >> 2;

n |= n >> 4;

n |= n >> 8;

n |= n >> 16;

// увеличить `n` и вернуться

return ++n;

}

public static void main(String[] args)

{

int n = 131;

System.out.println(“The next power of 2 is “ + findNextPowerOf2(n));

}

Скачать Выполнить код

результат:

The next power of 2 is 256

Python

# Вычислить следующую наивысшую степень двойки 32-битного числа `n`

def findNextPowerOf2(n):

# уменьшает `n` (для обработки случаев, когда `n` само по себе является степенью числа 2)

n = n – 1

# устанавливает все биты после последнего установленного бита

n |= n >> 1

n |= n >> 2

n |= n >> 4

n |= n >> 8

n |= n >> 16

# увеличивает `n` и возвращает

return n + 1

if __name__ == ‘__main__’:

n = 131

print(‘The next power of 2 is’, findNextPowerOf2(n))

Скачать Выполнить код

результат:

The next power of 2 is 256

Как работает сдвиг вправо и операция побитового ИЛИ?

Возьмем в качестве примера число 131, т.е. 10000011 в двоичном формате:

n--;             // 10000011 ——> 10000010
n |= n >> 1;    // 10000010 | 01000001 = 11000011
n |= n >> 2;    // 11000011 | 00110000 = 11110011
n |= n >> 4;    // 11110011 | 00001111 = 11111111
n |= n >> 8;    // … (At this point, all bits are 1, so further bitwise OR
n |= n >> 16;   // operations produce no effect)
n++;             // 11111111 ——> 100000000

Есть один бит в 9th положение, которое представляет 2⁸, что действительно является следующей по величине степенью числа 2. Каждый из сдвигов перекрывает все существующие биты 1 в числе с некоторыми ранее нетронутыми 0, в конечном итоге создавая общее количество битов 1, равное общему количеству битов в исходном числе. Добавление единицы к этому значению дает новую степень числа 2.

Есть несколько других возможных решений этой проблемы.

Использованная литература: https://graphics.stanford.edu/~seander/bithacks.html#SwappingBitsXOR

Источник

Указать ближайшее число степени двойки

Вопрос

Ответы

C++: степень двойки, ближайшая сверху к заданному числу

Подход 1

C++

Java

Python

C++

Java

Python

Подход 3

C++

Java

Python

Подход 4

C++

Java

Python

Как работает сдвиг вправо и операция побитового ИЛИ?

Вам также может понравиться

Как составить декларацию 3 ндфл при продаже дома

Как найти потерянный регион в майнкрафт

Как найти координаты точек без построения графика

Добавить комментарий Отменить ответ