Самый быстрый способ найти двоичную базу

Question

Я пытаюсь найти двоичную базу числа, например функцию пола, которая округляет число до наибольшего целого ниже, Я хочу округлить число до 1-й двоичной базы под ним.

Например:

for 1000 it should be 512 
for 10 it should be 8 
for 208 it should be 128 

Это то, что я пробовал. Я чувствую, что функции журнала будут потреблять больше ресурсов так есть ли более быстрый подход для этого?

#include<stdio.h> 
int main() { 
    unsigned long long int num; 
    unsigned long long int mask; 
    scanf("%llu", &num); 
    mask = 0x80000000; 
    while(mask >>= 1) { 
     if (mask & num) 
      break; 
    } 
    printf("%llu\n", mask); 
    return 0; 
} 

Спасибо :)

Answer 1

Представлять числа в двоичной системе, то искать наиболее значащий бит (самый высокий ненулевой бит). Наивно вы можете это сделать, переставив один бит за раз, пока он не станет равным нулю - это было «слишком много». Это в основном подход, который вы пробовали. Быстрее будет бинарный поиск. Для 32-битного целого, сдвиг вправо на 16; если все еще> 0, сдвиг вправо на 8 и т. д. Я уверен, что вы можете понять это здесь.

Пример кода:

typedef unsigned long long int ulli; 
ulli floor2(ulli num){ 
    int msb = 8*sizeof(num)/2; 
    ulli temp = ((ulli)1)<<msb; 
    while(msb>1){ 
    msb/=2; // using divide for clarity 
    if(temp>num) temp>>=msb; else temp<<=msb; 
    } 
    if (temp>num) temp/=2; 
    return temp; 
} 

Я провел несколько тестов этого алгоритма против topBit, а также метод builtIn. Цикл с итерациями 10M, генерирующий «длинное» случайное число, занимает 362 мс в моей системе (без оптимизации компилятора). Если цикл включает в себя один из методов расчета, раз увеличиваются следующим образом:

============= total net 
builtin:   407  45 
binary search: 579 215 
topBit:   2295 1933 

Встроенный метод, безусловно, самый быстрый с большим отрывом - на самом деле не удивительно! С 64-разрядными номерами topBit в среднем будет нуждаться в 32 циклах (половина бит устанавливается, поэтому пропускается) и бинарные только 5 циклов, поэтому вы ожидаете разницу в скорости 6x; это примерно то, что вы видите. Когда я определяю ulli как unsigned short (16 бит), разница во времени составляет около 2x.

Answer 2

Я предполагаю, что если число уже имеет силу 2 или ноль, оно должно быть возвращено без изменений. Только положительные числа.

int floor2(int n) 
{ 
    if ((n & (n-1)) == 0) 
     return n; 
    while (((n+1) & n) != 0) 
    { 
     n = n | (n+1); 
    } 
    return (n + 1) >> 1; 
} 

Фантазия немного вертел здесь имеет преимущество в том, что вычитание 1 из числа с одним битом (т.е. степень 2) устанавливает все биты под ним, при добавлении 1 к номеру будет установить самый низкий бит нуля.

Answer 3

Это проблема очень тесно связана с поиском наиболее значимой проблемы с битами; потому что после того, что это просто немного немного сдвигая:

Finding MSB хорошо описана здесь:

Find most significant bit (left-most) that is set in a bit array

, а затем вы делаете что-то вроде этого:

int foo = 1000; 
int bar = ((msb(foo) << 1) - 1) >> 1; 
if (bar > foo) bar = bar >> 1; 

и у вас есть ,

Если вы используете архитектуру Intel, вы можете использовать __builtin_clz (вычислять ведущие нули) в gcc для получения msb;

Или

Вот очень интересный способ сделать вычисления, ведущие нули без поддержки CPU

http://www.hackersdelight.org/hdcodetxt/nlz.c.txt

Answer 4

Это примерно в 2 раза быстрее, чем версия:

uint64_t g(uint64_t num) { 
    uint64_t r = 1; 
    num = num >> 1; 
    while(num>r) { 
     r <<= 1; 
    } 
    return r; 
} 

Answer 5

int topBit(int n) { 
    while (true){ 
     m = n & (n-1); 
     if (m == 0) return n; 
     n = m; 
    } 
} 

n & (n-1) очищает днище установить бит. Просто сделайте это, пока не достигнете нуля, а затем вы знаете, что предыдущее значение имело только один бит (самый высокий, который был установлен на входе).

Answer 6

int test(int num) { 
    int res = (num==0?0:1); 
    while(num>1) { 
     num=num>>1; 
     res=res<<1; 
    } 
    return res; 
} 

быстрее, чем ниже, когда число не велико.

Answer 7

Короткий и сладкий ...
(пример кода спрашивающий имела проблемы со значениями> = 0x80000000LLU, фиксирован.)
Это требует только 1 сравнения в петле, а не 2.

unsigned long long int MSMask(unsigned long long int) { 
    if (num == 0) { 
    return 0; 
    } 
    else { 
    unsigned long long int mask = 0x8000000000000000LLU; 
    while (!(mask & num)) mask >>= 1; 
    return mask; 
    } 
} 

Answer 8

худший случай производительность предложенного бита вертел фокусы может/должна быть улучшена путем постепенно or ИНГ несколько бит, чтобы быть из них:

int s=1; 
while ((n+1) & n) { 
    n|=n >> s; 
    s<<=1; 
} 
return (n+1) >> 1; 

Это осколочное выходы, когда все младшие значащие биты являются единицами, требующими только некоторые итерации log2 (log2 (n)).

Answer 9

Вы можете сделать это, используя GCC builtins, если вы компилируете GCC. Встроенный __builtin_clzll подсчитывает количество ведущих нулей в unsigned long long. Вы можете использовать его, чтобы вычислить положение самого старшего бита, а затем сдвиг влево 1, что много раз, чтобы получить ответ:

#include <limits.h> 

Затем используйте:

unsigned long long result = 
    num ? 1LLU << (sizeof(unsigned long long)*CHAR_BIT - __builtin_clzll(num) - 1) : 0; 

printf("%llu\n", result); 

Answer 10

This classic document есть много способов, чтобы найти пол (база 2) целого числа. После того, как вы нашли журнал, нужный номер, конечно, 1 < < log.

Самого увлекательное предложение это

// Find the integer log base 2 of an integer with an 64-bit IEEE float 
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; 

Код выше загружает 64-битный (IEEE-754 с плавающей точкой) в два раз с 32-разрядным целым числом (без paddding бит) путем хранения целое число в мантиссе, в то время как показатель степени равен 252. Из этого недавно измененного двойника вычитается значение 252 (выраженное как double), которое устанавливает результирующий показатель в базу данных 2 входного значения v. Все, что осталось сдвигает биты экспоненты в положение (20 бит справа) и вычитает смещение 0x3FF (которое равно 1023 десятичным). Этот метод занимает всего 5 операций, но многие процессоры медленно манипулируют удвоениями, и необходимо учитывать энтузиазм архитектуры.

Таким образом, конечный результат, который вы хотите, будет 1 << r. Обратите внимание, что манипуляция с удвоениями - намного больше быстрее, чем при написании этой статьи. Лучше всего в этом коде есть то, что он не содержит ветвей, поэтому будет хорошо конвейерно. Вы должны обязательно попробовать. У меня нет времени попробовать тест сейчас, но это было бы интересно.

Я не могу поручиться, что этот код соответствует стандарту C.

Answer 11

Я знаю рекурсия, как правило, не так эффективна, как итерации, но я не могу с собой поделать - я люблю хорошие рекурсии:

unsigned topBit(unsigned n) { 
    unsigned m = n & (n-1); 
    return m ? topBit(m) : n; 
} 

ДОБАВЛЕНИЯ: Фактические тайминги показали это как немного быстрее, чем @ Итеративная версия LaurenceGonsalves при компиляции с оптимизацией.