Вычисление пола log_2(x) с использованием только побитовых операторов в C

Question

Для домашней работы, используя C, я должен создать программу, которая находит базу журналов 2 с числом больше 0, используя только операторы! ~ & ^ | + << >>. Я знаю, что я должен сдвигаться вправо несколько раз, но я не знаю, как отследить количество раз без каких-либо циклов или ifs. Я застрял в этом вопросе в течение нескольких дней, поэтому любая помощь приветствуется.

int ilog2(int x) {

    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);

}

Это то, что я до сих пор. Я передаю самый важный бит до конца.

Answer 1

Это получает слово logbase2 числа.

int ilog2(int x) {

    int i, j, k, l, m;
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);

    // i = 0x55555555 
    i = 0x55 | (0x55 << 8); 
    i = i | (i << 16);

    // j = 0x33333333 
    j = 0x33 | (0x33 << 8);
    j = j | (j << 16);

    // k = 0x0f0f0f0f 
    k = 0x0f | (0x0f << 8);
    k = k | (k << 16);

    // l = 0x00ff00ff 
    l = 0xff | (0xff << 16);

    // m = 0x0000ffff 
    m = 0xff | (0xff << 8);

    x = (x & i) + ((x >> 1) & i);
    x = (x & j) + ((x >> 2) & j);
    x = (x & k) + ((x >> 4) & k);
    x = (x & l) + ((x >> 8) & l);
    x = (x & m) + ((x >> 16) & m);
    x = x + ~0;
    return x; 
}

Answer 2

Предполагает 32-разрядный unsigned int:

unsigned int ulog2 (unsigned int u)
{
    unsigned int s, t;

    t = (u > 0xffff) << 4; u >>= t;
    s = (u > 0xff  ) << 3; u >>= s, t |= s;
    s = (u > 0xf   ) << 2; u >>= s, t |= s;
    s = (u > 0x3   ) << 1; u >>= s, t |= s;

    return (t | (u >> 1));
}

---

Так как я предположил >Я думал, что найду способ избавиться от этого.

(u > 0xffff) эквивалентно: ((u >> 16) != 0), Если вычесть займы:
((u >> 16) - 1) установит MSB, если (u <= 0xffff), замещать -1 с +(~0) (позволил).

Итак, условие: (u > 0xffff) заменяется на: (~((u >> 16) + ~0U)) >> 31

---

unsigned int ulog2 (unsigned int u)
{
    unsigned int r = 0, t;

    t = ((~((u >> 16) + ~0U)) >> 27) & 0x10;
    r |= t, u >>= t;
    t = ((~((u >>  8) + ~0U)) >> 28) &  0x8;
    r |= t, u >>= t;
    t = ((~((u >>  4) + ~0U)) >> 29) &  0x4;
    r |= t, u >>= t;
    t = ((~((u >>  2) + ~0U)) >> 30) &  0x2;
    r |= t, u >>= t;

    return (r | (u >> 1));
}

Answer 3

Ваш результат - просто ранг самого высокого ненулевого бита.

int log2_floor (int x)
{
    int res = -1;
    while (x) { res++ ; x = x >> 1; }
    return res;
}

Одним из возможных решений является использование этого метода:

Он основан на аддитивности логарифмов:
log₂(2ⁿ x) = log₂(x) + n

Пусть x₀ будет числом 2n бит (например, n=16 для 32 бит).

если x₀ > 2ⁿ, мы можем определить x₁ так, чтобы x₀ = 2ⁿ x_1, и мы можем сказать, чтоE (log₂(x₀)) = n + E (log₂(x₁))
Мы можем вычислить x₁ с двоичным сдвигом:x₁ = x₀ >> n

В противном случае мы можем просто установить X₁ = X₀

Сейчас мы сталкиваемся с той же проблемой с оставшейся верхней или нижней половиной х₀

Разбивая x пополам на каждом шаге, мы можем в итоге вычислить E (log₂(x)):

int log2_floor (unsigned x)
{
    #define MSB_HIGHER_THAN(n) (x &(~((1<<n)-1)))
    int res = 0;
    if MSB_HIGHER_THAN(16) {res+= 16; $x >>= 16;}
    if MSB_HIGHER_THAN( 8) {res+=  8; $x >>=  8;}
    if MSB_HIGHER_THAN( 4) {res+=  4; $x >>=  4;}
    if MSB_HIGHER_THAN( 2) {res+=  2; $x >>=  2;}
    if MSB_HIGHER_THAN( 1) {res+=  1;}
    return res;
}

Так как ваш учитель-садист сказал, что вы не можете использовать циклы, мы можем взломать наш путь, вычислив значение, которое будет n в случае положительного теста и 0 в противном случае, таким образом, не влияя на сложение или сдвиг:

#define N_IF_MSB_HIGHER_THAN_N_OR_ELSE_0(n) (((-(x>>n))>>n)&n)

Если - оператор также запрещен оператором-психопатом (что глупо, поскольку процессоры могут обрабатывать дополнения до 2 так же, как и побитовые операции), вы можете использовать -x = ~x+1 в приведенной выше формуле

#define N_IF_MSB_HIGHER_THAN_N_OR_ELSE_0_WITH_NO_MINUS(n) (((~(x>>n)+1)>>n)&n)

что мы будем сокращать до NIMHTNOE0WNM для удобства чтения.

Также мы будем использовать | вместо + так как мы знаем, что они не будут нести.

Здесь пример для 32-битных целых чисел, но вы могли бы заставить его работать на 64, 128, 256, 512 или 1024-битных целых числах, если вам удалось найти язык, который поддерживает это большое целочисленное значение.

int log2_floor (unsigned x)
{
    #define NIMHTNOE0WNM(n) (((~(x>>n)+1)>>n)&n)

    int res, n;

    n = NIMHTNOE0WNM(16); res  = n; x >>= n;
    n = NIMHTNOE0WNM( 8); res |= n; x >>= n;
    n = NIMHTNOE0WNM( 4); res |= n; x >>= n;
    n = NIMHTNOE0WNM( 2); res |= n; x >>= n;
    n = NIMHTNOE0WNM( 1); res |= n;
    return res;
}

Ах, но, возможно, вам было запрещено использовать #define тоже? В этом случае я не могу сделать для вас намного больше, кроме как посоветовать вам забить своего учителя до смерти старым выпуском K&R.

Это приводит к бесполезному, запутанному коду, который выделяет сильный запах немытых хакеров 70-х годов.

В большинстве, если не во всех процессорах, реализованы специальные инструкции "считать начальные нули" (например, clz на ARM, bsr на x86 или cntlz на PowerPC), который может добиться цели без всей этой суеты.

Answer 4

Вам разрешено использовать & тогда вы можете использовать &&? С этим вы можете сделать условия без необходимости if

if (cond)
    doSomething();

может быть сделано с

cond && doSomething();

В противном случае, если вы хотите присвоить значение условно, как value = cond ? a : b; тогда вы можете сделать это с &

mask = -(cond != 0); // or mask = (cond != 0) << 31) >> 31;  // assuming int is 32 bits and use 2's complement
value = (mask & a) | (~mask & b);

Некоторым другим способом:

int v; // 32-bit integer to find the log base 2 of
int r; // result of log_2(v) goes here
union { unsigned int u[2]; double d; } t; // temp

t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] = 0x43300000;
t.u[__FLOAT_WORD_ORDER!=LITTLE_ENDIAN] = v;
t.d -= 4503599627370496.0;
r = (t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] >> 20) - 0x3FF;

или же

unsigned int v;          // 32-bit value to find the log2 of 
register unsigned int r; // result of log2(v) will go here
register unsigned int shift;

r =     (v > 0xFFFF) << 4; v >>= r;
shift = (v > 0xFF  ) << 3; v >>= shift; r |= shift;
shift = (v > 0xF   ) << 2; v >>= shift; r |= shift;
shift = (v > 0x3   ) << 1; v >>= shift; r |= shift;
                                        r |= (v >> 1);

по-другому

uint32_t v; // find the log base 2 of 32-bit v
int r;      // result goes here

static const int MultiplyDeBruijnBitPosition[32] = 
{
  0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
  8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};

v |= v >> 1; // first round down to one less than a power of 2 
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;

r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];

http://graphics.stanford.edu/~seander/bithacks.html

Answer 5

Вопрос равен "найти старший бит 1 двоичного числа"

ШАГ 1: установите слева от 1 все до 1, например, от 0x07000000 до 0x07ffffff

x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16); // number of ops = 10

ШАГ 2: возвращает количество цифр 1 в слове и минус 1

Ссылка: вес Хэмминга

// use bitCount
int m1 = 0x55; // 01010101...
m1 = (m1 << 8) + 0x55;
m1 = (m1 << 8) + 0x55;
m1 = (m1 << 8) + 0x55;
int m2 = 0x33; // 00110011...
m2 = (m2 << 8) + 0x33;
m2 = (m2 << 8) + 0x33;
m2 = (m2 << 8) + 0x33;
int m3 = 0x0f; // 00001111...
m3 = (m3 << 8) + 0x0f;
m3 = (m3 << 8) + 0x0f;
m3 = (m3 << 8) + 0x0f;

x = x + (~((x>>1) & m1) + 1); // x - ((x>>1) & m1)
x = (x & m2) + ((x >> 2) & m2);
x = (x + (x >> 4)) & m3;
// x = (x & m3) + ((x >> 4) & m3);

x += x>>8;
x += x>>16;

int bitCount =  x & 0x3f; // max 100,000(2) = 32(10)
// Number of ops: 35 + 10 = 45
return bitCount + ~0;

Это как я. Спасибо ~

Answer 6

Мне также назначили эту проблему для домашней работы, и я провел много времени, думая об этом, поэтому я думал, что поделюсь тем, что я придумал. Это работает с целыми числами на 32-битной машине.!!x возвращает, если x равен нулю или единице.

int ilog2(int x) {

    int byte_count = 0;
    int y = 0;

    //Shift right 8
    y = x>>0x8;
    byte_count += ((!!y)<<3);

    //Shift right 16
    y = x>>0x10;
    byte_count += ((!!y)<<3);

    //Shift right 24 and mask to adjust for arithmetic shift
    y = (x>>0x18)&0xff;
    byte_count += ((!!y)<<3);


    x = (x>>byte_count) & 0xff;

    x = x>>1;
    byte_count += !!x;
    x = x>>1;
    byte_count += !!x;
    x = x>>1;
    byte_count += !!x;
    x = x>>1;
    byte_count += !!x;
    x = x>>1;
    byte_count += !!x;
    x = x>>1;
    byte_count += !!x;
    x = x>>1;
    byte_count += !!x;
    x = x>>1;            //8
    byte_count += !!x;


    return byte_count;

}