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

Question

[uvelichitel]

Все в заголовке.
Как из
0001000000==128
получить
0001000000 -> 7
без

for n>0; k++{
n<<1
}
return k

Возможно?

Comments

[monah_tuk]

Подписался. Особенно если для ARM такое есть.

[monah_tuk]

Поправочка, для ARM926E-JS (ARM9E/ARMv5TEJ)

[monah_tuk]

Снова поправочка: инструкция CLZ (Counting Lead Zeros)
https://www.scss.tcd.ie/~waldroj/3d1/arm_arm.pdf страница 175. По задаче топик стартера:
sizeof(val)*8 - CLZ(val)

[3vi1_0n3]

P.S.: 128 = 1000 0000

Answer 1

[Antony]

Если у вас нет под рукой какого-нибудь специфичного процессора (или АЛУ), в котором есть такая операция - никак.

Comments

[uvelichitel]

Не нравится, что это так, но ответ нравится определенностью.)))

[Владимир Мартьянов]

Есть подозрение, что в x86 в расширении BMI/BMI2 подходящая инструкция уже есть.

Answer 2

[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

Answer 3

[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 лучше.

Answer 4

[Freeman]

На x86 -- BSF/BSR.

Answer 5

[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;
}

Comments

[Antony]

Параллелизм тут исключительно на совести компилятора.