ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Как определить - является ли число степенью 2?
25 сообщений из 26, страница 1 из 2
  1  все
Как определить - является ли число степенью 2?
    #39629387
Ролг Хупин
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Ролг Хупин
Участник
И если нет, то найти ближайшее целое, являющееся степенью 2?
...
Рейтинг: 0 / 0
12.04.2018, 18:00
| Ответить | Цитировать | Написать  
Как определить - является ли число степенью 2?
    #39629392
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
ЕМНИП
Код: sql
1.
x ~ (x-1) != 0


Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
12.04.2018, 18:08
| Ответить | Цитировать | Написать  
Как определить - является ли число степенью 2?
    #39629393
blonduser
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
blonduser
Участник
Ролг Хупин,
Возьмите логарифм по основанию два и будет вам счатье
...
Рейтинг: 0 / 0
12.04.2018, 18:08
| Ответить | Цитировать | Написать  
Как определить - является ли число степенью 2?
    #39629455
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
blonduserРолг Хупин,
Возьмите логарифм по основанию два и будет вам счатье
Вам счастье, а процессору жопа в виде расчета логарифма.

Ролг Хупин, задачу поподробней опиши.
...
Рейтинг: 0 / 0
12.04.2018, 20:10
| Ответить | Цитировать | Написать  
Как определить - является ли число степенью 2?
    #39629460
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ролг Хупин,

В книге Генри Уоррена описано большинство целочисленных трюков арифметики.
...
Рейтинг: 0 / 0
12.04.2018, 20:23
| Ответить | Цитировать | Написать  
Как определить - является ли число степенью 2?
    #39629477
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
Dimitry SibiryakovЕМНИП
Код: sql
1.
x ~ (x-1) != 0


Ну почти ))

Как-то так (только для беззнаковых):
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
bool is_power_of_2(size_t n)
{
    return n != 0 && (n & (n - 1)) == 0;
}

size_t next_power_of_2(size_t n)
{
    if (is_power_of_2(n))
        return n;
    size_t mask = 1;
    while (mask < n) {
        n |= mask;
        mask <<= 1;
    }
    n++;
    return n;
}
...
Рейтинг: 0 / 0
12.04.2018, 20:45
| Ответить | Цитировать | Написать  
Как определить - является ли число степенью 2?
    #39629493
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
Степени двойки, это все числа у которых установлен только один бит:
1 = 2^0 (00000001b)
2 = 2^1 (00000010b)
4 = 2^2 (00000100b)
8 = 2^3 (00001000b)
16 = 2^4 (00010000b)
32 = 2^5 (00100000b)
64 = 2^6 (01000000b)
и т.д.
...
Рейтинг: 0 / 0
12.04.2018, 21:17
| Ответить | Цитировать | Написать  
Как определить - является ли число степенью 2?
    #39629545
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Проверять битики - это играть по правилам регистровой арифметики CPU.

Вот вариант для символьных вычислений.

Код: javascript
1.
2.
3.
4.
5.
6.
def nextPowerOf2(x : BigInt) : BigInt = { 
 var k : BigInt = 1; 
 while(k < x) 
  k = k * 2;
 k 
}


Код: javascript
1.
2.
scala> nextPowerOf2(BigInt("99999999999999999999999999"))
res7: BigInt = 154742504910672534362390528
...
Рейтинг: 0 / 0
13.04.2018, 00:17
| Ответить | Цитировать | Написать  
Как определить - является ли число степенью 2?
    #39629684
Ролг Хупин
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Ролг Хупин
Участник
Dima TblonduserРолг Хупин,
Возьмите логарифм по основанию два и будет вам счатье
Вам счастье, а процессору жопа в виде расчета логарифма.

Ролг Хупин, задачу поподробней опиши.

Прикручиваю логгер, там есть параметр - размер очереди, он должен быть, по утверждению автора, степенью 2.
Но параметр передаеся юзером, и я хочу определить, если не тсепень двойки, то дотянуть до ближайшего числа степени двойик и подкорректировать.
...
Рейтинг: 0 / 0
13.04.2018, 10:42
| Ответить | Цитировать | Написать  
Как определить - является ли число степенью 2?
    #39629719
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Проверка положительного числа на степень двойки
Код: plaintext
1.
(x & (x - 1)) == 0



Для поиска ближайшего большего если производительность не критична
Код: plaintext
1.
2.
n = 1;
while(n < x) n <<= 1;
...
Рейтинг: 0 / 0
13.04.2018, 11:27
| Ответить | Цитировать | Написать  
Как определить - является ли число степенью 2?
    #39629729
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Anatoly MoskovskyКак-то так (только для беззнаковых):
Код: plaintext
1.
2.
3.
4.
bool is_power_of_2(size_t n)
{
    return n != 0 && (n & (n - 1)) == 0;
}


n != 0 тут лишнее, т.к. 0 & -1 == 0
...
Рейтинг: 0 / 0
13.04.2018, 11:38
| Ответить | Цитировать | Написать  
Как определить - является ли число степенью 2?
    #39629731
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Dima TAnatoly MoskovskyКак-то так (только для беззнаковых):
Код: plaintext
1.
2.
3.
4.
bool is_power_of_2(size_t n)
{
    return n != 0 && (n & (n - 1)) == 0;
}


n != 0 тут лишнее, т.к. 0 & -1 == 0
Извиняюсь, затупил, 0 это ведь не степень двойки
...
Рейтинг: 0 / 0
13.04.2018, 11:39
| Ответить | Цитировать | Написать  
Как определить - является ли число степенью 2?
    #39629738
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
Dima T0 это ведь не степень двойки
Ну в каком-то смысле иногда 0 можно считать степенью 2, просто оно дробное и в целом представлении дает 0 (точное значение 0.5)
...
Рейтинг: 0 / 0
13.04.2018, 11:46
| Ответить | Цитировать | Написать  
Как определить - является ли число степенью 2?
    #39629768
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Ролг Хупин,

Трюки - манипуляции c битами
...
Рейтинг: 0 / 0
13.04.2018, 12:25
| Ответить | Цитировать | Написать  
Как определить - является ли число степенью 2?
    #39629851
Ролг Хупин
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Ролг Хупин
Участник
Dima TПроверка положительного числа на степень двойки
Код: plaintext
1.
(x & (x - 1)) == 0



Для поиска ближайшего большего если производительность не критична
Код: plaintext
1.
2.
n = 1;
while(n < x) n <<= 1;



Не думаю, что производительность просядет на этом коде.
...
Рейтинг: 0 / 0
13.04.2018, 13:57
| Ответить | Цитировать | Написать  
Как определить - является ли число степенью 2?
    #39629888
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Нашел побыстрее алгоритм
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
int next_power_of_2(int x) {
	x |= x >> 1;
	x |= x >> 2;
	x |= x >> 4;
	x |= x >> 8;
	x |= x >> 16;
	return (x - (x >> 1)) << 1;
}


Взято тут
...
Рейтинг: 0 / 0
13.04.2018, 14:36
| Ответить | Цитировать | Написать  
Как определить - является ли число степенью 2?
    #39629900
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
Ролг ХупинИ если нет, то найти ближайшее целое, являющееся степенью 2?

В бинарном представлении числа должна быть только одна бинарная единица.
...
Рейтинг: 0 / 0
13.04.2018, 14:48
| Ответить | Цитировать | Написать  
Как определить - является ли число степенью 2?
    #39629970
Котовасия
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Котовасия
Участник
MasterZivРолг ХупинИ если нет, то найти ближайшее целое, являющееся степенью 2?

В бинарном представлении числа должна быть только одна бинарная единица.
Код: plaintext
1.
(signed int) 0x80000000;


:)
...
Рейтинг: 0 / 0
13.04.2018, 15:38
| Ответить | Цитировать | Написать  
Как определить - является ли число степенью 2?
    #39629974
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
MasterZivВ бинарном представлении числа должна быть только одна бинарная единица.Это у целого числа, являющегося степенью двойки, а если в целом больше одного установленного бита, то процедура нахождения ближайшего не на много сложнее - если сразу за самым старшим, установленным в 1 битом, в сторону более младших разрядов следует 1, то надо маскировать все младшие биты и результат сдвинуть влево на один, а если следует 0, то просто маскировать все младшие биты.
...
Рейтинг: 0 / 0
13.04.2018, 15:39
| Ответить | Цитировать | Написать  
Как определить - является ли число степенью 2?
    #39629986
Котовасия
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Котовасия
Участник
Ролг Хупин...то найти ближайшее целое, являющееся степенью 2?
Создаем массив целых, большой... [INT_MAX] (т.е. 0..2147483647)
Заполняем его по принципу: если индекс равен степени двойки - заносим в элемент с этим индексом значение индекса, иначе - заносим ближайшее, равное степени двойки (просто смотрим, какая из двух соседних степеней "ближе").
Это на первом этапе не очень быстро, да. Зато потом любое число определяется волшебным способом, просто вытаскиванием из массива по индексу, равному тестируемому числу... главное - чтобы памяти хватило... :)
...
Рейтинг: 0 / 0
13.04.2018, 15:50
| Ответить | Цитировать | Написать  
Как определить - является ли число степенью 2?
    #39629988
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
rdb_devMasterZivВ бинарном представлении числа должна быть только одна бинарная единица.Это у целого числа, являющегося степенью двойки, а если в целом больше одного установленного бита, то процедура нахождения ближайшего не на много сложнее - если сразу за самым старшим, установленным в 1 битом, в сторону более младших разрядов следует 1, то надо маскировать все младшие биты и результат сдвинуть влево на один, а если следует 0, то просто маскировать все младшие биты.
Это понятно, тут проблема маску получить для конкретного числа.
...
Рейтинг: 0 / 0
13.04.2018, 15:51
| Ответить | Цитировать | Написать  
Как определить - является ли число степенью 2?
    #39629993
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
КотовасияСоздаем массив целых, большой... [INT_MAX] (т.е. 0..2147483647)
...
главное - чтобы памяти хватило... :)
8 Гб под это безобразие ... мдя ...

И не факт что будет быстрее чем эти 5 действий 21336940 , т.к. обращение к памяти отсутствующей в кэше проца достаточно много времени занимает.
...
Рейтинг: 0 / 0
13.04.2018, 15:56
| Ответить | Цитировать | Написать  
Как определить - является ли число степенью 2?
    #39630036
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
Dima TЭто понятно, тут проблема маску получить для конкретного числа.Что же ты за программист, если такая элементарная задача, как получение маски сдвигом, для тебя - проблема?
...
Рейтинг: 0 / 0
13.04.2018, 17:15
| Ответить | Цитировать | Написать  
Как определить - является ли число степенью 2?
    #39630070
Ролг Хупин
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Ролг Хупин
Участник
КотовасияРолг Хупин...то найти ближайшее целое, являющееся степенью 2?
Создаем массив целых, большой... [INT_MAX] (т.е. 0..2147483647)
Заполняем его по принципу: если индекс равен степени двойки - заносим в элемент с этим индексом значение индекса, иначе - заносим ближайшее, равное степени двойки (просто смотрим, какая из двух соседних степеней "ближе").
Это на первом этапе не очень быстро, да. Зато потом любое число определяется волшебным способом, просто вытаскиванием из массива по индексу, равному тестируемому числу... главное - чтобы памяти хватило... :)

данунафиг
...
Рейтинг: 0 / 0
13.04.2018, 18:48
| Ответить | Цитировать | Написать  
Как определить - является ли число степенью 2?
    #39630088
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
rdb_devDima TЭто понятно, тут проблема маску получить для конкретного числа.Что же ты за программист, если такая элементарная задача, как получение маски сдвигом, для тебя - проблема?
Да, хреновый программист, знал что можно получить результат в 5 действий для 32-х битного числа, но не смог придумать как. Гуглить пришлось 21336940
...
Рейтинг: 0 / 0
13.04.2018, 19:56
| Ответить | Цитировать | Написать  
25 сообщений из 26, страница 1 из 2
  1  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Как определить - является ли число степенью 2?
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]