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


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

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

В книге Генри Уоррена описано большинство целочисленных трюков арифметики.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.04.2018, 20:45
    #39629477
Anatoly Moskovsky
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как определить - является ли число степенью 2?
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, 21:17
    #39629493
rdb_dev
rdb_dev
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как определить - является ли число степенью 2?
Степени двойки, это все числа у которых установлен только один бит:
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
| Ответить | Цитировать | Написать  
13.04.2018, 00:17
    #39629545
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как определить - является ли число степенью 2?
Проверять битики - это играть по правилам регистровой арифметики 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, 10:42
    #39629684
Ролг Хупин
Ролг Хупин
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как определить - является ли число степенью 2?
Dima TblonduserРолг Хупин,
Возьмите логарифм по основанию два и будет вам счатье
Вам счастье, а процессору жопа в виде расчета логарифма.

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

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



Для поиска ближайшего большего если производительность не критична
Код: plaintext
1.
2.
n = 1;
while(n < x) n <<= 1;
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.04.2018, 11:38
    #39629729
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как определить - является ли число степенью 2?
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:39
    #39629731
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как определить - является ли число степенью 2?
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:46
    #39629738
Anatoly Moskovsky
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как определить - является ли число степенью 2?
Dima T0 это ведь не степень двойки
Ну в каком-то смысле иногда 0 можно считать степенью 2, просто оно дробное и в целом представлении дает 0 (точное значение 0.5)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.04.2018, 12:25
    #39629768
kealon(Ruslan)
kealon(Ruslan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как определить - является ли число степенью 2?
Ролг Хупин,

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



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



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

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

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


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

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

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


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