очевидно, найти индекс набора старших бит 32-битного числа без циклов

Question

Вот сложный вопрос (по крайней мере, мне было трудно: P):

найти индекс набора старших бит 32-битного числа без использования циклов.

Answer 1

С рекурсией:

int firstset(int bits) {        
     return (bits & 0x80000000) ? 31 : firstset((bits << 1) | 1) - 1;
}

• Предполагается [31,..,0] индексирование
• Возвращает -1, если биты не установлены
• | 1 предотвращает переполнение стека, ограничивая количество смен, пока не будет достигнут 1 (32)
• Не рекурсивно:)

Answer 2

Этаж логарифма-основания-два должен сделать свое дело (хотя вы должны использовать специальный случай 0).

Floor of log base 2 of 0001 is 0 (bit with index 0 is set).
 "           "      of 0010 is 1 (bit with index 1 is set).
 "           "      of 0011 is 1 (bit with index 1 is set).
 "           "      of 0100 is 2 (bit with index 2 is set).
and so on.

---

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

Ваш начальник не придет к вам однажды и скажет: «Эй, у нас есть срочная работа для этой последней функции, и ее нужно реализовать без петель!»

Answer 3

Вы можете сделать это так (не оптимизировано):

int index = 0;
uint32_t temp = number;

if ((temp >> 16) != 0) {
    temp >>= 16;
    index += 16;
}

if ((temp >> 8) != 0) {
    temp >>= 8
    index += 8;
}

...

Answer 4

Извините, что натолкнулся на старую ветку, но как на счет этого

inline int ilog2(unsigned long long i) {
  union { float f; int i; } = { i }; 
  return (u.i>>23)-27;
}
...
int highest=ilog2(x); highest+=(x>>highest)-1;
// and in case you need it
int lowest = ilog2((x^x-1)+1)-1;

Answer 5

это можно сделать как двоичный поиск, уменьшая сложность от O (N) (для N-разрядного слова) до O (log (N)).Возможная реализация:

int highest_bit_index(uint32_t value)
{ 
  if(value == 0) return 0;
  int depth = 0;
  int exponent = 16;

  while(exponent > 0)
  {
    int shifted = value >> (exponent);
    if(shifted > 0)
    {
      depth += exponent;
      if(shifted == 1) return depth + 1;
      value >>= exponent;
    }
    exponent /= 2;
  }

  return depth + 1;
}

вход представляет собой 32-разрядное целое число без знака.у него есть цикл, который может быть преобразован в 5 уровней операторов if, в результате чего получается около 32 операторов if.Вы также можете использовать рекурсию, чтобы избавиться от цикла, или от абсолютно злого «goto»;)

Answer 6

Обратите внимание, что вы пытаетесь вычислить целое число log2 из целого числа,

#include <stdio.h>
#include <stdlib.h>

unsigned int
Log2(unsigned long x)
{
    unsigned long n = x;
    int bits = sizeof(x)*8;
    int step = 1; int k=0;
    for( step = 1; step < bits; ) {
        n |= (n >> step);
        step *= 2; ++k;
    }
    //printf("%ld %ld\n",x, (x - (n >> 1)) );
    return(x - (n >> 1));
}

Обратите внимание, что вы можете пытаться искать более 1 бита за раз.

unsigned int
Log2_a(unsigned long x)
{
    unsigned long n = x;
    int bits = sizeof(x)*8;
    int step = 1;
    int step2 = 0;
    //observe that you can move 8 bits at a time, and there is a pattern...
    //if( x>1<<step2+8 ) { step2+=8;
        //if( x>1<<step2+8 ) { step2+=8;
            //if( x>1<<step2+8 ) { step2+=8;
            //}
        //}
    //}
    for( step2=0; x>1L<<step2+8; ) {
        step2+=8;
    }
    //printf("step2 %d\n",step2);
    for( step = 0; x>1L<<(step+step2); ) {
        step+=1;
        //printf("step %d\n",step+step2);
    }
    printf("log2(%ld) %d\n",x,step+step2);
    return(step+step2);
}

Этот подход использует бинарный поиск

unsigned int
Log2_b(unsigned long x)
{
    unsigned long n = x;
    unsigned int bits = sizeof(x)*8;
    unsigned int hbit = bits-1;
    unsigned int lbit = 0;
    unsigned long guess = bits/2;
    int found = 0;

    while ( hbit-lbit>1 ) {
        //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        //when value between guess..lbit
        if( (x<=(1L<<guess)) ) {
           //printf("%ld < 1<<%d %ld\n",x,guess,1L<<guess);
            hbit=guess;
            guess=(hbit+lbit)/2;
            //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        }
        //when value between hbit..guess
        //else
        if( (x>(1L<<guess)) ) {
            //printf("%ld > 1<<%d %ld\n",x,guess,1L<<guess);
            lbit=guess;
            guess=(hbit+lbit)/2;
            //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        }
    }
    if( (x>(1L<<guess)) ) ++guess;
    printf("log2(x%ld)=r%d\n",x,guess);
    return(guess);
}

Другой метод двоичного поиска, возможно, более читабельный,

unsigned int
Log2_c(unsigned long x)
{
    unsigned long v = x;
    unsigned int bits = sizeof(x)*8;
    unsigned int step = bits;
    unsigned int res = 0;
    for( step = bits/2; step>0; )
    {
        //printf("log2(%ld) v %d >> step %d = %ld\n",x,v,step,v>>step);
        while ( v>>step ) {
            v>>=step;
            res+=step;
            //printf("log2(%ld) step %d res %d v>>step %ld\n",x,step,res,v);
        }
        step /= 2;
    }
    if( (x>(1L<<res)) ) ++res;
    printf("log2(x%ld)=r%ld\n",x,res);
    return(res);
}

И поскольку вы захотите проверить это,

int main()
{
    unsigned long int x = 3;
    for( x=2; x<1000000000; x*=2 ) {
        //printf("x %ld, x+1 %ld, log2(x+1) %d\n",x,x+1,Log2(x+1));
        printf("x %ld, x+1 %ld, log2_a(x+1) %d\n",x,x+1,Log2_a(x+1));
        printf("x %ld, x+1 %ld, log2_b(x+1) %d\n",x,x+1,Log2_b(x+1));
        printf("x %ld, x+1 %ld, log2_c(x+1) %d\n",x,x+1,Log2_c(x+1));
    }
    return(0);
}

Answer 7

Решение Пейсли на самом деле довольно легко сделать хвостовой рекурсией, хотя это гораздо более медленное решение, чем рекомендуемый этаж (log2 (n));

int firstset_tr(int bits, int final_dec) {

     // pass in 0 for final_dec on first call, or use a helper function

     if (bits & 0x80000000) {
      return 31-final_dec;
     } else {
      return firstset_tr( ((bits << 1) | 1), final_dec+1 );
     }
}

Эта функция также работает для других размеров бит, просто измените проверку, например,

if (bits & 0x80) {   // for 8-bit
  return 7-final_dec;
}

Answer 8

int high_bit_set(int n, int pos)
{
if(pos<0) 
return -1;
else
return (0x80000000 & n)?pos:high_bit_set((n<<1),--pos);
}

main()
{
int n=0x23;
int high_pos = high_bit_set(n,31);
printf("highest index = %d",high_pos);
}

Из функции основного вызова high_bit_set(int n , int pos) со значением ввода n и значением по умолчанию 31 в качестве самой высокой позиции.И функция, как указано выше.

Answer 9

Пусть n - десятичное число, для которого определяется местоположение бита начало - указывает десятичное значение (1 << 32) - 2147483648 bitLocation - указывает местоположение бита, которое установлено в 1 </p>

public int highestBitSet(int n, long start, int bitLocation)
{
    if (start == 0)
    {
        return 0;
    }
    if ((start & n) > 0)
    {
        return bitLocation;
    }
    else
    {
        return highestBitSet(n, (start >> 1), --bitLocation);
    }
}

    long i = 1;
    long startIndex = (i << 31);
    int bitLocation = 32;
    int value = highestBitSet(64, startIndex, bitLocation);
    System.out.println(value);

Answer 10

хорошо из того, что я знаю, функция Log реализована очень эффективно в большинстве языков программирования, и даже если она содержит циклы, их, вероятно, очень мало, поэтому я бы сказал, что в большинстве случаев использование журнала будетбыстрее и прямее.Вы должны проверить на 0 и избегать записи журнала 0, так как это приведет к сбою программы.