uvelichitel
@uvelichitel
habrahabr.ru/users/uvelichitel

Можно ли одной bitwise операцией (без циклического сдвига) определить степень двойки(номер бита)?

Все в заголовке.
Как из
0001000000==128
получить
0001000000 -> 7
без
for n>0; k++{
n<<1
}
return k

Возможно?
  • Вопрос задан
  • 422 просмотра
Решения вопроса 5
RiseOfDeath
@RiseOfDeath
Диванный эксперт.
Если у вас нет под рукой какого-нибудь специфичного процессора (или АЛУ), в котором есть такая операция - никак.
Ответ написан
@monah_tuk
Для ARM нашёл CLZ (Counting Lead Zeros)
https://www.scss.tcd.ie/~waldroj/3d1/arm_arm.pdf страница 175.

не одна bitwise (вычитание добавить нужно), но зато без цикла.

Теперь не процессоро-специфичное, но компиляторо-специфичное.
GCC:
  • __builtin_clz() - число лидирующих нулей
  • __builtin_ctz() - число оконченых нулей
  • __builtin_popcount() - число единиц в числе

https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
www.go4expert.com/articles/builtin-gcc-functions-b...
Понятно, что эффективность будет зависеть от того, есть ли реализация на конкретном CPU подобающей команды.

Вот тут:
stackoverflow.com/questions/355967/how-to-use-msvc...
https://msdn.microsoft.com/en-us/library/wfd9z0bb.aspx
отсылка к реализации MSVC
Ответ написан
Mrrl
@Mrrl
Заводчик кардиганов
Можно взять остаток от деления на 37, и дальше по табличке. Но это может оказаться дороже, чем цикл.
Или за 5 операций AND:

int n=0;
if(x&0xffff0000) n+=16;
if(x&0xff00ff00) n+=8;
if(x&0xf0f0f0f0) n+=4;
if(x&0xcccccccc) n+=2;
if(x&0xaaaaaaaa) n++;

Хотя через CLZ лучше.
Ответ написан
@SilentFl
Одной никак не получится. Но если есть мысль делать эту операцию для многих чисел, да параллельно - то можно так
#include <stdio.h>

int f(int n) {
  	int k = 0;
  if((n & 0xFFFF) == 0)   k = 16, n >>= 16;
  if((n & 0x00FF) == 0)   k += 8, n >>= 8;
  if((n & 0x000F) == 0)   k += 4, n >>= 4;
  if((n & 0x0003) == 0)   k += 2, n >>= 2;
  if((n & 0x0001) == 0)   k += 1;
  	return k;
}

int main(void) {
  printf("%d\n", f(128));
  	return 0;
}
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы