У меня есть реализация битового массива, где 0-й индекс является MSB первого байта в массиве, 8-й индекс является MSB второго байта и т.д.
Какой быстрый способ найти первый бит, который установлен в этом битовом массиве? Все связанные с этим решения, которые я искал, находят первый наименее значащий бит, но мне нужен первый наиболее важный. Итак, учитывая 0x00A1, я хочу 8 (так как это 9-й бит слева).
GCC имеет __builtin_clz, который переводит на BSR на x86/x64, CLZ на ARM и т.д. и эмулирует инструкцию, если аппаратное обеспечение не реализуйте его.
Visual С++ 2005 и выше _BitScanReverse.
Являясь производителем junkie, я пробовал массу вариаций для набора MSB, следующее самое быстрое, с которым я столкнулся,
unsigned int msb32(unsigned int x)
{
static const unsigned int bval[] =
{0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4};
unsigned int r = 0;
if (x & 0xFFFF0000) { r += 16/1; x >>= 16/1; }
if (x & 0x0000FF00) { r += 16/2; x >>= 16/2; }
if (x & 0x000000F0) { r += 16/4; x >>= 16/4; }
return r + bval[x];
}
ТЛ: д - р; Для 32 битов используйте умножение де Брюина.
Это самый быстрый переносимый алгоритм. Это значительно быстрее и правильнее, чем все другие переносимые 32-битные алгоритмы MSB в этом потоке.
Алгоритм де Брюйна также возвращает правильный результат, когда ввод равен нулю. Инструкции __builtin_clz и _BitScanReverse возвращают неверные результаты, когда ввод равен нулю.
На x86-64 умножение де Брюина выполняется со скоростью, сравнимой с эквивалентными (ошибочными) инструкциями аппаратного обеспечения, с разницей в производительности всего около 3%.
Здесь код.
u32 msbDeBruijn32( u32 v )
{
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;
return MultiplyDeBruijnBitPosition[( u32 )( v * 0x07C4ACDDU ) >> 27];
}
Все остальные ответы в этой теме либо работают намного хуже, чем предлагают их авторы, либо неправильно рассчитывают результат, либо и то, и другое. Пусть сравнят их все, и пусть проверят, что они делают то, что, как они утверждают, делают.
Вот простой С++ 11, чтобы проверить все эти реализации. Он компилируется чисто в Visual Studio, но должен работать на всех современных компиляторах. Это позволяет запускать тест в режиме производительности (bVerifyResults = false) и в режиме проверки (bVerifyResults = true).
Вот результаты в режиме проверки:
Verification failed for msbNative64: input was 0; output was 818af060; expected 0
Verification failed for msbFfs: input was 22df; output was 0; expected d
Verification failed for msbPerformanceJunkie32: input was 0; output was ffffffff; expected 0
Verification failed for msbNative32: input was 0; output was 9ab07060; expected 0
"Производители-наркоманы" и собственные реализации Microsoft делают разные вещи, когда ввод равен нулю. msbPerformanceJunkie32 выдает -1, а Microsoft _BitScanReverse выдает случайное число, соответствующее базовой аппаратной инструкции. Также реализация msbPerformanceJunkie32 выдает результат, который отличается от всех остальных ответов.
Вот результаты в режиме производительности на моем ноутбуке i7-4600, скомпилированные в режиме выпуска:
msbLoop64 took 2.56751 seconds
msbNative64 took 0.222197 seconds
msbLoop32 took 1.43456 seconds
msbFfs took 0.525097 seconds
msbPerformanceJunkie32 took 1.07939 seconds
msbDeBruijn32 took 0.224947 seconds
msbNative32 took 0.218275 seconds
Версия de Bruijn значительно превосходит другие реализации, потому что она не имеет ответвлений и поэтому хорошо работает с входами, которые производят равномерно распределенный набор выходов. Все остальные версии медленнее по сравнению с произвольными входами из-за штрафов за неправильное предсказание ветвления на современных процессорах. Функция smbFfs выдает неверные результаты, поэтому ее можно игнорировать.
Некоторые реализации работают на 32-битных входах, а некоторые на 64-битных входах. Шаблон поможет нам сравнить яблоки с яблоками, независимо от размера ввода.
Здесь код. Скачайте и запустите тесты самостоятельно, если хотите.
#include <iostream>
#include <chrono>
#include <random>
#include <cassert>
#include <string>
#include <limits>
#ifdef _MSC_VER
#define MICROSOFT_COMPILER 1
#include <intrin.h>
#endif // _MSC_VER
const int iterations = 100000000;
bool bVerifyResults = false;
std::random_device rd;
std::default_random_engine re(rd());
typedef unsigned int u32;
typedef unsigned long long u64;
class Timer
{
public:
Timer() : beg_(clock_::now()) {}
void reset() {
beg_ = clock_::now();
}
double elapsed() const {
return std::chrono::duration_cast<second_>
(clock_::now() - beg_).count();
}
private:
typedef std::chrono::high_resolution_clock clock_;
typedef std::chrono::duration<double, std::ratio<1> > second_;
std::chrono::time_point<clock_> beg_;
};
unsigned int msbPerformanceJunkie32(u32 x)
{
static const unsigned int bval[] =
{ 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4 };
unsigned int r = 0;
if (x & 0xFFFF0000) {
r += 16 / 1;
x >>= 16 / 1;
}
if (x & 0x0000FF00) {
r += 16 / 2;
x >>= 16 / 2;
}
if (x & 0x000000F0) {
r += 16 / 4;
x >>= 16 / 4;
}
return r + bval[x];
}
#define FFS(t) \
{ \
register int n = 0; \
if (!(0xffff & t)) \
n += 16; \
if (!((0xff << n) & t)) \
n += 8; \
if (!((0xf << n) & t)) \
n += 4; \
if (!((0x3 << n) & t)) \
n += 2; \
if (!((0x1 << n) & t)) \
n += 1; \
return n; \
}
unsigned int msbFfs32(u32 x)
{
FFS(x);
}
unsigned int msbLoop32(u32 x)
{
int r = 0;
if (x < 1) return 0;
while (x >>= 1) r++;
return r;
}
unsigned int msbLoop64(u64 x)
{
int r = 0;
if (x < 1) return 0;
while (x >>= 1) r++;
return r;
}
u32 msbDeBruijn32(u32 v)
{
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;
return MultiplyDeBruijnBitPosition[(u32)(v * 0x07C4ACDDU) >> 27];
}
#ifdef MICROSOFT_COMPILER
u32 msbNative32(u32 val)
{
unsigned long result;
_BitScanReverse(&result, val);
return result;
}
u32 msbNative64(u64 val)
{
unsigned long result;
_BitScanReverse64(&result, val);
return result;
}
#endif // MICROSOFT_COMPILER
template <typename InputType>
void test(unsigned int msbFunc(InputType),
const std::string &name,
const std::vector< InputType > &inputs,
std::vector< unsigned int > &results,
bool bIsReference = false
)
{
if (bIsReference)
{
int i = 0;
for (int i = 0; i < iterations; i++)
results[i] = msbFunc(inputs[i]);
}
InputType result;
if (bVerifyResults)
{
bool bNotified = false;
for (int i = 0; i < iterations; i++)
{
result = msbFunc(inputs[i]);
if ((result != results[i]) && !bNotified)
{
std::cout << "Verification failed for " << name << ": "
<< "input was " << std::hex << inputs[i]
<< "; output was " << result
<< "; expected " << results[i]
<< std::endl;
bNotified = true;
}
}
}
else
{
Timer t;
for (int i = 0; i < iterations; i++)
{
result = msbFunc(inputs[i]);
}
double elapsed = t.elapsed();
if ( !bIsReference )
std::cout << name << " took " << elapsed << " seconds" << std::endl;
if (result == -1.0f)
std::cout << "this comparison only exists to keep the compiler from " <<
"optimizing out the benchmark; this branch will never be called";
}
}
void main()
{
std::uniform_int_distribution <u64> dist64(0,
std::numeric_limits< u64 >::max());
std::uniform_int_distribution <u32> shift64(0, 63);
std::vector< u64 > inputs64;
for (int i = 0; i < iterations; i++)
{
inputs64.push_back(dist64(re) >> shift64(re));
}
std::vector< u32 > results64;
results64.resize(iterations);
test< u64 >(msbLoop64, "msbLoop64", inputs64, results64, true);
test< u64 >(msbLoop64, "msbLoop64", inputs64, results64, false);
#ifdef MICROSOFT_COMPILER
test< u64 >(msbNative64, "msbNative64", inputs64, results64, false);
#endif // MICROSOFT_COMPILER
std::cout << std::endl;
std::uniform_int_distribution <u32> dist32(0,
std::numeric_limits< u32 >::max());
std::uniform_int_distribution <u32> shift32(0, 31);
std::vector< u32 > inputs32;
for (int i = 0; i < iterations; i++)
inputs32.push_back(dist32(re) >> shift32(re));
std::vector< u32 > results32;
results32.resize(iterations);
test< u32 >(msbLoop32, "msbLoop32", inputs32, results32, true);
test< u32 >(msbLoop32, "msbLoop32", inputs32, results32, false);
test< u32 >(msbFfs32, "msbFfs", inputs32, results32, false);
test< u32 >(msbPerformanceJunkie32, "msbPerformanceJunkie32",
inputs32, results32, false);
test< u32 >(msbDeBruijn32, "msbDeBruijn32", inputs32, results32, false);
#ifdef MICROSOFT_COMPILER
test< u32 >(msbNative32, "msbNative32", inputs32, results32, false);
#endif // MICROSOFT_COMPILER
}
Существует несколько способов сделать это, и относительная производительность различных реализаций несколько зависит от машины (я, по-видимому, сравнивал это в некоторой степени с аналогичной целью). На некоторых машинах есть даже встроенная инструкция для этого (используйте один, если он доступен, и переносимость может быть рассмотрена).
Ознакомьтесь с некоторыми реализациями здесь (в разделе "целочисленная база базы 2" ). Если вы используете GCC, проверьте функции __builtin_clz и __builtin_clzl (которые делают это для ненулевых целых чисел без знака и беззнаковых длин, соответственно). "Clz" означает "подсчет ведущих нулей", что является еще одним способом описания одной и той же проблемы.
Конечно, если ваш бит-массив не вписывается в подходящее машинное слово, вам нужно перебирать слова в массиве, чтобы найти первое ненулевое слово, а затем выполнить этот расчет только на этом слове.
Посмотрите на инструкцию BSR (бит сканирования назад) x86 asm для быстрого выполнения этой задачи. Из документа Intel:
Searches the source operand (second operand) for the most significant set bit (1 bit).
If a most significant 1 bit is found, its bit index is stored in the destination operand
(first operand).
http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
Если вы используете x86, вы можете выполнять практически любое побайтовое или поэтапное решение, используя операции SSE2, в сочетании с инструкциями find-first-bit, которые (в мире gcc) произносится как "ffs" для младшего бит и "fls" для самого высокого бита. Прошу прощения за ошибку (! @# $% ^) Форматирование кода "C" в ответе; проверять, выписываться: http://mischasan.wordpress.com/2011/11/03/sse2-bit-trick-ffsfls-for-xmm-registers/
Я работал с несколькими функциями, чтобы получить самый старший бит, но проблемы обычно возникают между 32 и 64-битными номерами или перемещаются между блоками x86_64 и x86. Функции __builtin_clz, __builtin_clzl и __builtin_clzll хорошо работают для 32/64 разрядных номеров и на машинах x86_64 и x86. Однако требуются три функции. Я нашел простой MSB, который полагается на сдвиг вправо, который будет обрабатывать все случаи для положительных чисел. По крайней мере, для использования, которое я делаю, он преуспел там, где другие не удалось:
int
getmsb (unsigned long long x)
{
int r = 0;
if (x < 1) return 0;
while (x >>= 1) r++;
return r;
}
Обозначив ввод как unsigned long long, он может обрабатывать все числовые классы от unsigned char до unsigned long long и с учетом стандартного определения, он совместим с моделями x86_64 и x86. Случай 0 определяется как возвращаемый 0, но может быть изменен по мере необходимости. Простой тест и вывод:
int
main (int argc, char *argv[]) {
unsigned char c0 = 0;
unsigned char c = 216;
unsigned short s = 1021;
unsigned int ui = 32768;
unsigned long ul = 3297381253;
unsigned long long ull = 323543844043;
int i = 32767;
printf (" %16u MSB : %d\n", c0, getmsb (c0));
printf (" %16u MSB : %d\n", c, getmsb (c));
printf (" %16u MSB : %d\n", s, getmsb (s));
printf (" %16u MSB : %d\n", i, getmsb (i));
printf (" %16u MSB : %d\n", ui, getmsb (ui));
printf (" %16lu MSB : %d\n", ul, getmsb (ul));
printf (" %16llu MSB : %d\n", ull, getmsb (ull));
return 0;
}
Вывод:
0 MSB : 0
216 MSB : 7
1021 MSB : 9
32767 MSB : 14
32768 MSB : 15
3297381253 MSB : 31
323543844043 MSB : 38
ПРИМЕЧАНИЕ: для соображений скорости, используя одну функцию для выполнения того же объекта с центром вокруг __builtin_clzll, все еще быстрее примерно в 6 раз.
Два лучших способа, которые я знаю, чтобы сделать это в чистом C:
Сначала линейный поиск массива byte/word, чтобы найти первый байт/слово, отличное от нуля, затем выполните развернутый двоичный поиск найденного байта/слова.
if (b>=0x10)
if (b>=0x40)
if (b>=0x80) return 0;
else return 1;
else
if (b>=0x20) return 2;
else return 3;
else
if (b>=0x4)
if (b>=0x8) return 4;
else return 5;
else
if (b>=0x2) return 6;
else return 7;
3 (BTW, что log2 (8)) условные прыжки, чтобы получить ответ. На современных машинах x86 последний будет оптимизирован для условного mov.
В качестве альтернативы используйте таблицу поиска для сопоставления байта с индексом первого установленного бита.
Связанная тема, которую вы, возможно, захотите найти, - это целые функции log2. Если я помню, ffmpeg имеет приятную реализацию.
Изменить: вы можете сделать вышеупомянутый бинарный поиск бездисковым двоичным поиском, но я не уверен, что в этом случае он будет более эффективным...
Не самый быстрый, но он работает...
//// C program
#include <math.h>
#define POS_OF_HIGHESTBIT(a) /* 0th position is the Least-Signif-Bit */ \
((unsigned) log2(a)) /* thus: do not use if a <= 0 */
#define NUM_OF_HIGHESTBIT(a) ((!(a)) \
? 0 /* no msb set*/ \
: (1 << POS_OF_HIGHESTBIT(a) ))
// could be changed and optimized, if it is known that the following NEVER holds: a <= 0
int main()
{
unsigned a = 5; // 0b101
unsigned b = NUM_OF_HIGHESTBIT(a); // 4 since 4 = 0b100
return 0;
}
Здесь фрагмент кода, объясняющий __builtin_clz()
////// go.c ////////
#include <stdio.h>
unsigned NUM_BITS_U = ((sizeof(unsigned) << 3) - 1);
#define POS_OF_HIGHESTBITclz(a) (NUM_BITS_U - __builtin_clz(a)) /* only works for a != 0 */
#define NUM_OF_HIGHESTBITclz(a) ((a) \
? (1U << POS_OF_HIGHESTBITclz(a)) \
: 0)
int main()
{
unsigned ui;
for (ui = 0U; ui < 18U; ++ui)
printf("%i \t %i\n", ui, NUM_OF_HIGHESTBITclz(ui));
return 0;
}
Я добавлю один!
typedef unsigned long long u64;
typedef unsigned int u32;
typedef unsigned char u8;
u8 findMostSignificantBit (u64 u64Val)
{
u8 u8Shift;
u8 u8Bit = 0;
assert (u64Val != 0ULL);
for (u8Shift = 32 ; u8Shift != 0 ; u8Shift >>= 1)
{
u64 u64Temp = u64Val >> u8Shift;
if (u64Temp)
{
u8Bit |= u8Shift; // notice not using +=
u64Val = u64Temp;
}
}
return u8Bit;
}
Конечно, это работает с 64-разрядным номером (unsigned long long), а не с массивом. Кроме того, многие люди указали на встроенные функции g++, о которых я не знал. Как интересно.
Во всяком случае, это находит самый значительный бит в 6 итерациях и дает утверждение, если вы передали 0 функции. Не самая лучшая функция для использования, если у вас есть доступ к инструкции набора микросхем.
Я также использую | = вместо + =, потому что они всегда являются степенями двух, а OR (классически) быстрее, чем добавление. Поскольку я добавляю только уникальные способности 2 вместе, я никогда не перекатился.
Это двоичный поиск, который означает, что он всегда находит результат в 6 итерациях.
Опять же, это лучше:
u8 findMostSignificantBit2 (u64 u64Val)
{
assert (u64Val != 0ULL);
return (u8) (__builtin_ctzll(u64Val));
}
Вот простой алгоритм грубой силы для массива байтов произвольного размера:
int msb( unsigned char x); // prototype for function that returns
// most significant bit set
unsigned char* p;
for (p = arr + num_elements; p != arr;) {
--p;
if (*p != 0) break;
}
// p is with pointing to the last byte that has a bit set, or
// it pointing to the first byte in the array
if (*p) {
return ((p - arr) * 8) + msb( *p);
}
// what do you want to return if no bits are set?
return -1;
Я оставлю это как упражнение для читателя, чтобы найти подходящую функцию msb(), а также оптимизацию для работы с деталями данных int или long long.
Um, тэг указывает 32 бит, но похоже, что значения, которые вы используете, - 16 бит. Если вы имели в виду 32 бит, тогда я думаю, что ответ для 0x00a1 должен быть 24, а не 8.
Предполагая, что вы ищете индекс бит MSB с левой стороны, и вы знаете, что вы будете иметь дело только с uint32_t, здесь очевидный простой алгоритм:
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
int main()
{
uint32_t test_value = 0x00a1;
int i;
for (i=0; i<32; ++i)
{
if (test_value & (0x80000000 >> i))
{
printf("i = %d\n", i);
exit(0);
}
}
return 0;
}
В x86 есть инструкция BSR, которая возвращает битовый индекс (а не количество ведущих нулей над ним).
Но, к сожалению, нет переносимого встроенного кода, который бы эффективно использовал его для всех компиляторов. GNU C предоставляет __builtin_clz, но unsigned bitidx = 31 - __builtin_clz(x); не оптимизировать обратно до просто BSR с текущими GCC и ICC. (Это происходит с clang, который доказывает, что выражение эквивалентно, так что может).
Следующее определяет макросы или функции BSR32() и BSR64() которые эффективно компилируются в инструкцию bsr на x86. (Вывод результата "мусор", если входные данные были нулевыми. При использовании встроенных функций невозможно воспользоваться преимуществом поведения инструкции asm, если оставить назначение без изменений для input = 0.)
Переносимость на не-x86 потребует некоторого дополнительного #ifdef например, чтобы вернуться к 31-__builtin_clz. Большинство не-x86 ISA, если у них вообще есть бит с нулем в начале, считают начальные нули вместо того, чтобы дать вам битовый индекс. Вот почему GNU C определяет __builtin_clz как переносимый встроенный модуль. (Если в целевой системе нет поддержки HW, встроенная программа будет компилироваться в программную эмуляцию, обычно вызывая вспомогательную функцию libgcc.)
#include <stdint.h>
// define BSR32() and BSR64()
#if defined(_MSC_VER) || defined(__INTEL_COMPILER)
#ifdef __INTEL_COMPILER
typedef unsigned int bsr_idx_t;
#else
#include <intrin.h> // MSVC
typedef unsigned long bsr_idx_t;
#endif
static inline
unsigned BSR32(unsigned long x){
bsr_idx_t idx;
_BitScanReverse(&idx, x); // ignore bool retval
return idx;
}
static inline
unsigned BSR64(uint64_t x) {
bsr_idx_t idx;
_BitScanReverse64(&idx, x); // ignore bool retval
return idx;
}
#elif defined(__GNUC__)
#ifdef __clang__
static inline unsigned BSR64(uint64_t x) {
return 63-__builtin_clzll(x);
// gcc/ICC can't optimize this back to just BSR, but clang can and doesn't provide alternate intrinsics
}
#else
#define BSR64 __builtin_ia32_bsrdi
#endif
#include <x86intrin.h>
#define BSR32(x) _bit_scan_reverse(x)
#endif
bsf вероятно, не нуждается в такой большой помощи для компиляторов, потому что встроенная функция соответствует поведению команды asm, возвращающему битовый индекс LSB, то есть количество завершающих нулей.
Вызывающий тест unsigned test32(unsigned x) { return BSR32(x); } unsigned test32(unsigned x) { return BSR32(x); } содержит 1 инструкцию для всех основных компиляторов x86 в проводнике компилятора Godbolt. BSR64 также встроен в 64-битную версию размера операнда. См. Также Существует ли инструкция x86/x86_64, которая обнуляет все биты ниже старшего значащего бита? например, варианты использования.
;; x64 MSVC 19.16 -O2
unsigned int test32(unsigned int) PROC ; test32, COMDAT
bsr eax, ecx
ret 0
unsigned int test32(unsigned int) ENDP ; test32
# clang -O3 -march=haswell is too "smart?" for its own good:
test32(unsigned int):
lzcnt eax, edi
xor eax, 31
ret
# gcc8.2 -O3 -march=haswell
test32(unsigned int):
bsr eax, edi
ret
# ICC19 -O3 -march=haswell
test32(unsigned int):
bsr eax, edi #15.9
ret #41.12
Смысл этого состоит в том, чтобы избежать медленного кода из портативной (не MSVC) версии:
#ifdef __GNUC__
unsigned badgcc(uint64_t x) {
return 63 - __builtin_clzll(x);
}
#endif
Без -march=haswell мы получаем только BSR от clang, но:
# gcc8.2 -O3
badgcc(unsigned long):
bsr rdi, rdi
mov eax, 63
xor rdi, 63
sub eax, edi
ret
# ICC19.0.1 -O3
badgcc(unsigned long):
mov rax, -1 #46.17
bsr rdx, rdi #46.17
cmove rdx, rax #46.17
neg rdx #46.17
add rdx, 63 #46.17
neg edx #46.17
add edx, 63 #46.17
mov eax, edx #46.17
ret #46.17
Это просто противно. (Интересно видеть, что ICC делает CMOV для создания -1 если вход равен нулю. BSR устанавливает ZF в соответствии со своим входом, в отличие от большинства инструкций, которые устанавливают флаги в соответствии с результатом.)
С -march=haswell (или иным образом разрешающим использование инструкций BMI1) это не так плохо, но все же не так хорошо, как просто BSR. Выходные зависимости по модулю, которые компиляторы в основном работают, чтобы избежать для lzcnt, но, как ни странно, не для BSR. (Где выходная зависимость является истинной зависимостью из-за поведения input = 0.) Почему нарушение "выходной зависимости" LZCNT имеет значение?
#define FFS(t) \
({ \
register int n = 0; \
\
if (!(0xffff & t)) \
n += 16; \
\
if (!((0xff << n) & t)) \
n += 8; \
\
if (!((0xf << n) & t)) \
n += 4; \
\
if (!((0x3 << n) & t)) \
n += 2; \
\
if (!((0x1 << n) & t)) \
n += 1; \
\
n; \
})