Поиск позиции младшего значащего бита в O (1) времени [dубликат]
Легко читаемое решение, возможно, не самое эффективное:
function arrayUnique ($ myArray) {if (! is_array ($ myArray)) возвращает $ myArray; foreach ($ myArray as & amp; $ myvalue) {$ myvalue = serialize ($ myvalue); } $ myArray = array_unique ($ myArray); foreach ($ myArray as & amp; $ myvalue) {$ myvalue = unserialize ($ myvalue); } return $ myArray; } 22 ответа
Бит Twiddling Hacks предлагает отличную коллекцию, er, bit twiddling hacks, с обсуждением производительности / оптимизации. Мое любимое решение вашей проблемы (с этого сайта) - «умножить и искать»:
unsigned int v; // find the number of trailing zeros in 32-bit v
int r; // result goes here
static const int MultiplyDeBruijnBitPosition[32] =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];
Полезные ссылки:
"Использование последовательностей Bruijn для индексации 1 в компьютере Word "- Объяснение, почему работает вышеуказанный код. «Представление совета директоров> Битовые биты> BitScan» - Детальный анализ этой проблемы с уделением особого внимания программированию шахмат-
1Почему нисходящий? Это, возможно, самая быстрая реализация, в зависимости от скорости умножения. Это, конечно, компактный код, и трюк (v & amp; -v) - это то, чему все должны учиться и запоминать. – Adam Davis 16 April 2009 в 18:52
-
2+1 очень круто, насколько дорого стоит операция умножения, хотя по сравнению с операцией if (X & amp; Y)? – Brian R. Bondy 16 April 2009 в 19:05
-
3Кто-нибудь знает, как производительность этого сравнивается с __builtin_ffsl или ffsl? – Steven Lu 9 December 2012 в 02:46
-
4@Jim Balter, но modulo очень медленный по сравнению с умножением на современное оборудование. Поэтому я бы не назвал это лучшим решением. – Apriori 28 March 2014 в 03:37
-
5Мне кажется, что оба значения 0x01 и 0x00 приводят к значению 0 из массива. Очевидно, этот трюк будет указывать, что младший бит установлен, если 0 передано! – abelenky 16 September 2016 в 03:16
Weee, множество решений, а не контрольный показатель. Вы, должно быть, вам стыдитесь, -)
Моя машина - Intel i530 (2,9 ГГц), работающая под управлением Windows 7 64-бит. Я скомпилирован с 32-разрядной версией MinGW.
$ gcc --version
gcc.exe (GCC) 4.7.2
$ gcc bench.c -o bench.exe -std=c99 -Wall -O2
$ bench
Naive loop. Time = 2.91 (Original questioner)
De Bruijn multiply. Time = 1.16 (Tykhyy)
Lookup table. Time = 0.36 (Andrew Grant)
FFS instruction. Time = 0.90 (ephemient)
Branch free mask. Time = 3.48 (Dan / Jim Balter)
Double hack. Time = 3.41 (DocMax)
$ gcc bench.c -o bench.exe -std=c99 -Wall -O2 -march=native
$ bench
Naive loop. Time = 2.92
De Bruijn multiply. Time = 0.47
Lookup table. Time = 0.35
FFS instruction. Time = 0.68
Branch free mask. Time = 3.49
Double hack. Time = 0.92
Мой код:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ARRAY_SIZE 65536
#define NUM_ITERS 5000 // Number of times to process array
int find_first_bits_naive_loop(unsigned nums[ARRAY_SIZE])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
unsigned value = nums[i];
if (value == 0)
continue;
unsigned pos = 0;
while (!(value & 1))
{
value >>= 1;
++pos;
}
total += pos + 1;
}
}
return total;
}
int find_first_bits_de_bruijn(unsigned nums[ARRAY_SIZE])
{
static const int MultiplyDeBruijnBitPosition[32] =
{
1, 2, 29, 3, 30, 15, 25, 4, 31, 23, 21, 16, 26, 18, 5, 9,
32, 28, 14, 24, 22, 20, 17, 8, 27, 13, 19, 7, 12, 6, 11, 10
};
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
unsigned int c = nums[i];
total += MultiplyDeBruijnBitPosition[((unsigned)((c & -c) * 0x077CB531U)) >> 27];
}
}
return total;
}
unsigned char lowestBitTable[256];
int get_lowest_set_bit(unsigned num) {
unsigned mask = 1;
for (int cnt = 1; cnt <= 32; cnt++, mask <<= 1) {
if (num & mask) {
return cnt;
}
}
return 0;
}
int find_first_bits_lookup_table(unsigned nums[ARRAY_SIZE])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
unsigned int value = nums[i];
// note that order to check indices will depend whether you are on a big
// or little endian machine. This is for little-endian
unsigned char *bytes = (unsigned char *)&value;
if (bytes[0])
total += lowestBitTable[bytes[0]];
else if (bytes[1])
total += lowestBitTable[bytes[1]] + 8;
else if (bytes[2])
total += lowestBitTable[bytes[2]] + 16;
else
total += lowestBitTable[bytes[3]] + 24;
}
}
return total;
}
int find_first_bits_ffs_instruction(unsigned nums[ARRAY_SIZE])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
total += __builtin_ffs(nums[i]);
}
}
return total;
}
int find_first_bits_branch_free_mask(unsigned nums[ARRAY_SIZE])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
unsigned value = nums[i];
int i16 = !(value & 0xffff) << 4;
value >>= i16;
int i8 = !(value & 0xff) << 3;
value >>= i8;
int i4 = !(value & 0xf) << 2;
value >>= i4;
int i2 = !(value & 0x3) << 1;
value >>= i2;
int i1 = !(value & 0x1);
int i0 = (value >> i1) & 1? 0 : -32;
total += i16 + i8 + i4 + i2 + i1 + i0 + 1;
}
}
return total;
}
int find_first_bits_double_hack(unsigned nums[ARRAY_SIZE])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
unsigned value = nums[i];
double d = value ^ (value - !!value);
total += (((int*)&d)[1]>>20)-1022;
}
}
return total;
}
int main() {
unsigned nums[ARRAY_SIZE];
for (int i = 0; i < ARRAY_SIZE; i++) {
nums[i] = rand() + (rand() << 15);
}
for (int i = 0; i < 256; i++) {
lowestBitTable[i] = get_lowest_set_bit(i);
}
clock_t start_time, end_time;
int result;
start_time = clock();
result = find_first_bits_naive_loop(nums);
end_time = clock();
printf("Naive loop. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits_de_bruijn(nums);
end_time = clock();
printf("De Bruijn multiply. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits_lookup_table(nums);
end_time = clock();
printf("Lookup table. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits_ffs_instruction(nums);
end_time = clock();
printf("FFS instruction. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits_branch_free_mask(nums);
end_time = clock();
printf("Branch free mask. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits_double_hack(nums);
end_time = clock();
printf("Double hack. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
}
-
1Ориентиры как для де Бройна, так и для поиска могут вводить в заблуждение - сидя в таком замкнутом цикле, после первой операции таблицы поиска для каждого типа будут закреплены в кеше L1 до последнего цикла. Это вряд ли соответствует реальному использованию. – MattW 5 May 2015 в 18:02
-
2Я удивлен, что FFS не быстрее, чем LUT. Ваши тестовые данные rand() будут иметь нулевой байт с байтом только один раз в 256 раз, поэтому ветвь прогнозирует очень хорошо. На Godbolt внутренняя петля gcc4.7.2 -m32 -O2 -march=corei7 идет от .L13 до jne .L13, когда первый байт отличен от нуля и должен иметь хорошую пропускную способность на вашем процессоре Nehalem и просто узкое место по его пропускной способности из 9 совпадающих доменов, при теоретическом максимуме 4 за часы. Мне пришлось обрезать код до двух функций, иначе URL-адрес слишком длинный, чтобы godbolt сокращался с goo.gl. : / – Peter Cordes 18 December 2016 в 05:14
-
3Для входов с нулем в младшем байте он получает более высокие байты, сохраняя / перезагружая вместо переключения, из-за приведения указателя. (совершенно ненужное BTW и делает его зависимым от конца в отличие от сдвига). Во всяком случае, не только нереалистичность микрообнаружения из-за горячего кеша, но и предварительные схемы ветвления и тесты, которые очень хорошо предсказывают и делают LUT меньше работать. Многие реальные варианты использования имеют более равномерное распределение результатов, а не входных данных. – Peter Cordes 18 December 2016 в 05:17
-
4К сожалению, ваш цикл FFS замедляется ложной зависимостью в инструкции BSF, которую ваш харкий старый компилятор не избегает (, но более новый gcc должен, такой же для popcnt / lzcnt / tzcnt . [F1] имеет ложная зависимость от его вывода (поскольку фактическое поведение, когда input = 0, должно оставить выход неизменным). gcc, к сожалению, превращает это в зависимую от цикла зависимость, не очищая регистр между итерациями цикла. Таким образом, цикл должен работать на один на 5 циклов, узких мест в BSF (3) + CMOV (2) латентности. – Peter Cordes 18 December 2016 в 05:26
-
5Да, выполнение вне порядка может перекрывать несколько итераций цикла, если bsf ecx, [ebx+edx*4] не рассматривал ecx как вход, который ему пришлось ждать. (ECX в последний раз был написан CMOV предыдущего итератора). Но ЦП действительно ведет себя таким образом, чтобы реализовать «оставить dest unmodified, если источник равен нулю». (таким образом, это не действительно ложный оттиск, как для TZCNT, требуется зависимость данных, потому что не существует разветвления + спекулятивное выполнение в предположении, что вход отличен от нуля). Мы могли бы преодолеть это, добавив xor ecx,ecx до bsf, чтобы разорвать зависимость от ECX. – Peter Cordes 19 December 2016 в 00:19
Самое быстрое (не внутреннее / неассемблерное) решение для этого - найти младший байт, а затем использовать этот байт в таблице поиска с 256 входами. Это дает вам худшую производительность четырех условных инструкций и наилучшего варианта 1. Это не только наименьшее количество инструкций, но и наименьшее количество ветвей, что очень важно для современного оборудования.
Ваша таблица (256 8-разрядных записей) должна содержать индекс LSB для каждого номера в диапазоне 0-255. Вы проверяете каждый байт своего значения и находите самый младший ненулевой байт, затем используйте это значение для поиска реального индекса.
Для этого требуется 256-байтовая память, но если скорость этой функции равна так важно, чтобы 256-байты это достойно,
Например
byte lowestBitTable[256] = {
.... // left as an exercise for the reader to generate
};
unsigned GetLowestBitPos(unsigned value)
{
// note that order to check indices will depend whether you are on a big
// or little endian machine. This is for little-endian
byte* bytes = (byte*)value;
if (bytes[0])
return lowestBitTable[bytes[0]];
else if (bytes[1])
return lowestBitTable[bytes[1]] + 8;
else if (bytes[2])
return lowestBitTable[bytes[2]] + 16;
else
return lowestBitTable[bytes[3]] + 24;
}
-
1На самом деле это худший случай из трех условностей :) Но да, это самый быстрый подход (и обычно то, что люди ищут в таких вопросах интервью). – Brian 16 April 2009 в 18:47
-
2
-
3Любая таблица поиска увеличивает вероятность промаха в кэше и может понести стоимость доступа к памяти, которая может быть на несколько порядков выше, чем выполнение инструкций. – Mehrdad Afshari 16 April 2009 в 19:08
-
4я бы даже использовал бит-сдвиги (каждый раз меняя его на 8). может быть сделано полностью с использованием регистров. используя указатели, вам придется получить доступ к памяти. – Johannes Schaub - litb 16 April 2009 в 22:31
-
5Разумное решение, но между потенциалом для таблицы поиска, которая не находится в кеше (которая может быть решена, как указано), и количеством ветвей (потенциальное неверное предсказание), я предпочитаю многократно-поисковое решение (никаких ветвей, меньшая таблица поиска). Конечно, если вы можете использовать встроенные или встроенные сборки, они, вероятно, лучший выбор. Тем не менее, это решение не плохо. – Dan 14 January 2011 в 19:18
Вы можете проверить, установлен ли какой-либо бит младшего порядка. Если это так, посмотрите на нижний порядок оставшихся бит. например:
32bit int - проверка, задан ли какой-либо из первых 16. Если да, проверьте, установлен ли какой-либо из первых 8. если это так, ....
если нет, проверьте, установлен ли какой-либо из верхних 16 ..
По существу это двоичный поиск.
unsigned GetLowestBitPos(unsigned value)
{
if (value & 1) return 1;
if (value & 2) return 2;
if (value & 4) return 3;
if (value & 8) return 4;
if (value & 16) return 5;
if (value & 32) return 6;
if (value & 64) return 7;
if (value & 128) return 8;
if (value & 256) return 9;
if (value & 512) return 10;
if (value & 1024) return 11;
if (value & 2048) return 12;
if (value & 4096) return 13;
if (value & 8192) return 14;
if (value & 16384) return 15;
if (value & 32768) return 16;
if (value & 65536) return 17;
if (value & 131072) return 18;
if (value & 262144) return 19;
if (value & 524288) return 20;
if (value & 1048576) return 21;
if (value & 2097152) return 22;
if (value & 4194304) return 23;
if (value & 8388608) return 24;
if (value & 16777216) return 25;
if (value & 33554432) return 26;
if (value & 67108864) return 27;
if (value & 134217728) return 28;
if (value & 268435456) return 29;
if (value & 536870912) return 30;
return 31;
}
50% всех чисел вернутся в первую строку кода.
75% всех чисел вернутся к первым двум строкам кода.
87 % всех чисел вернется в первых трех строках кода.
94% всех чисел вернутся в первых 4 строках кода.
97% всех чисел вернутся в первых 5 строках кода.
и т. д.
Я думаю, что люди, жалующиеся на то, как неэффективный худший сценарий для этого кода не понимают, насколько редко это условие произойдет .
-
1
-
2
-
3Не мог ли этот по крайней мере превратиться в переключатель ...? – Steven Lu 9 December 2012 в 02:45
-
4«Не удалось ли это, по меньшей мере, превратить в переключатель ...? & quot; Вы пытались сделать это, прежде чем предполагать, что это возможно? Так как, когда вы можете делать вычисления прямо в случаях переключения? Это таблица поиска, а не класс. – j riv 5 July 2018 в 11:21
Это может быть сделано с наихудшим случаем менее 32 операций:
Это может быть сделано с наихудшим случаем менее 32 операций: Проверка на 2 или более бит так же эффективно, как проверка на 1 бит.
Так, например, нет ничего, что мешает вам проверить, для какой группировки его сначала, затем проверяя каждый бит от наименьшего до самого большого в этой группе.
Итак ... если вы проверите 2 бит в то время, когда у вас есть в худшем случае (Nbits / 2) + 1 общее количество проверок. если вы проверите 3 бита за раз, когда у вас есть в худшем случае (Nbits / 3) + 2, проверите общее количество. ...
Оптимальное было бы проверять группы из 4. Для чего потребуется в худшем случае 11 операций вместо вашего 32.
Лучший случай идет от проверки 1 ваших алгоритмов хотя до 2 проверок, если вы используете эту идею группировки. Но эта дополнительная 1 проверка в лучшем случае стоит того, чтобы сэкономить наихудший случай.
Примечание: я пишу это полностью, вместо того, чтобы использовать цикл, потому что он более эффективен таким образом.
int getLowestBitPos(unsigned int value)
{
//Group 1: Bits 0-3
if(value&0xf)
{
if(value&0x1)
return 0;
else if(value&0x2)
return 1;
else if(value&0x4)
return 2;
else
return 3;
}
//Group 2: Bits 4-7
if(value&0xf0)
{
if(value&0x10)
return 4;
else if(value&0x20)
return 5;
else if(value&0x40)
return 6;
else
return 7;
}
//Group 3: Bits 8-11
if(value&0xf00)
{
if(value&0x100)
return 8;
else if(value&0x200)
return 9;
else if(value&0x400)
return 10;
else
return 11;
}
//Group 4: Bits 12-15
if(value&0xf000)
{
if(value&0x1000)
return 12;
else if(value&0x2000)
return 13;
else if(value&0x4000)
return 14;
else
return 15;
}
//Group 5: Bits 16-19
if(value&0xf0000)
{
if(value&0x10000)
return 16;
else if(value&0x20000)
return 17;
else if(value&0x40000)
return 18;
else
return 19;
}
//Group 6: Bits 20-23
if(value&0xf00000)
{
if(value&0x100000)
return 20;
else if(value&0x200000)
return 21;
else if(value&0x400000)
return 22;
else
return 23;
}
//Group 7: Bits 24-27
if(value&0xf000000)
{
if(value&0x1000000)
return 24;
else if(value&0x2000000)
return 25;
else if(value&0x4000000)
return 26;
else
return 27;
}
//Group 8: Bits 28-31
if(value&0xf0000000)
{
if(value&0x10000000)
return 28;
else if(value&0x20000000)
return 29;
else if(value&0x40000000)
return 30;
else
return 31;
}
return -1;
}
-
1+1 от меня. Это не самый быстрый, но он быстрее оригинала, и это было ... – Andrew Grant 16 April 2009 в 19:02
-
2@ onebyone.livejournal.com: Даже если в коде была ошибка, концепция группировки - это тот момент, который я пытался преодолеть. Фактический пример кода не имеет большого значения, и его можно сделать более компактным, но менее эффективным. – Brian R. Bondy 16 April 2009 в 19:10
-
3Мне просто интересно, есть ли какая-то плохая часть моего ответа, или если людям это не нравится, я написал это полностью? – Brian R. Bondy 16 April 2009 в 19:11
-
4@ onebyone.livejournal.com: Когда вы сравниваете 2 алгоритма, вы должны сравнивать их так, как они есть, не предполагая, что на фазу оптимизации будет изменено волшебство. Я никогда не утверждал, что мой алгоритм был «быстрее». или. Только это меньше операций. – Brian R. Bondy 16 April 2009 в 20:08
-
5@ onebyone.livejournal.com: ... Мне не нужно профилировать вышеуказанный код, чтобы знать, что это меньше операций. Я вижу это ясно. Я никогда не делал никаких претензий, требующих профилирования. – Brian R. Bondy 16 April 2009 в 20:08
Еще одно решение, а не самое быстрое, но кажется довольно хорошим. По крайней мере, у нее нет ветвей. ;)
uint32 x = ...; // 0x00000001 0x0405a0c0 0x00602000
x |= x << 1; // 0x00000003 0x0c0fe1c0 0x00e06000
x |= x << 2; // 0x0000000f 0x3c3fe7c0 0x03e1e000
x |= x << 4; // 0x000000ff 0xffffffc0 0x3fffe000
x |= x << 8; // 0x0000ffff 0xffffffc0 0xffffe000
x |= x << 16; // 0xffffffff 0xffffffc0 0xffffe000
// now x is filled with '1' from the least significant '1' to bit 31
x = ~x; // 0x00000000 0x0000003f 0x00001fff
// now we have 1's below the original least significant 1
// let's count them
x = x & 0x55555555 + (x >> 1) & 0x55555555;
// 0x00000000 0x0000002a 0x00001aaa
x = x & 0x33333333 + (x >> 2) & 0x33333333;
// 0x00000000 0x00000024 0x00001444
x = x & 0x0f0f0f0f + (x >> 4) & 0x0f0f0f0f;
// 0x00000000 0x00000006 0x00000508
x = x & 0x00ff00ff + (x >> 8) & 0x00ff00ff;
// 0x00000000 0x00000006 0x0000000d
x = x & 0x0000ffff + (x >> 16) & 0x0000ffff;
// 0x00000000 0x00000006 0x0000000d
// least sign.bit pos. was: 0 6 13
-
1чтобы получить все 1 s от младшего значащего 1 до LSB, вместо этого используйте ((x & -x) - 1) << 1 – phuclv 12 June 2014 в 07:09
-
2
См. мой ответ здесь, как это сделать с помощью одной инструкции x86, за исключением того, что для поиска наименее значимого бита набора вам понадобится команда BSF («бит сканирования вперед») вместо BSR, описанная там ,
Вдохновленный этой подобной записью, которая включает в себя поиск набора бит, я предлагаю следующее:
unsigned GetLowestBitPos(unsigned value)
{
double d = value ^ (value - !!value);
return (((int*)&d)[1]>>20)-1023;
}
Плюсы:
нет циклов Нет разветвлений в постоянном времени обрабатывает значение = 0, возвращая результат в противном случае, только две строки кодаМинусы:
no loops предполагает, что double является вещественным * Обновление IEEE 754. Как отмечено в комментариях, объединение является более чистой реализацией (по крайней мере, для C) и будет выглядеть так:
unsigned GetLowestBitPos(unsigned value)
{
union {
int i[2];
double d;
} temp = { .d = value ^ (value - !!value) };
return (temp.i[1] >> 20) - 1023;
}
Предполагается, что 32-битные ints с минимально-ориентированным хранилищем для всех (думаю, процессоры x86).
-
1Интересно - я все еще боюсь использовать двойники для бит-арифметики, но я буду помнить об этом – peterchen 20 April 2009 в 09:02
-
2
-
3Тип-кастинг с помощью указателя-литья небезопасен в C или C ++. Используйте memcpy в C ++ или объединение в C. (Или объединение в C ++, если ваш компилятор гарантирует его безопасность. Например, расширения GNU для C ++ (поддерживаемые многими компиляторами) гарантируют, что тип объединения запрещен.) – Peter Cordes 3 August 2017 в 11:57
-
4Старые gcc также делают лучший код с объединением, а не с помощью указателя: он перемещается непосредственно из FP reg (xmm0) в rax (с movq) вместо хранения / перезагрузки. Новые gcc и clang используют movq для обоих способов. См. [D0] godbolt.org/g/x7JBiL для версии объединения. Преднамеренно ли вы делаете арифметический сдвиг на 20? В ваших предположениях также следует указать, что int - int32_t, а подписанный сдвиг вправо - это арифметический сдвиг (в C ++ он определяется реализацией) – Peter Cordes 3 August 2017 в 12:11
-
5Кроме того, BTW, Visual Studio (по крайней мере, 2013 г.) также использует подход test / setcc / sub. Мне больше нравится cmp / adc. – DocMax 5 August 2017 в 00:30
Если у вас есть ресурсы, вы можете пожертвовать памятью, чтобы улучшить скорость:
static const unsigned bitPositions[MAX_INT] = { 0, 0, 1, 0, 2, /* ... */ };
unsigned GetLowestBitPos(unsigned value)
{
assert(value != 0); // handled separately
return bitPositions[value];
}
Если Эта таблица будет потреблять не менее 4 ГБ (16 ГБ, если мы оставляем возвращаемый тип как unsigned).
Если ваша функция должна оставаться переносной и работать как можно быстрее любой ценой, это будет путь , В большинстве реальных приложений таблица 4 ГБ нереальна.
-
1
-
2Диапазон ввода уже указан типом параметра - «unsigned» - это 32-битное значение, поэтому нет, вы не в порядке. – Brian 16 April 2009 в 18:33
-
3ммм ... твоя мифическая система и ОС имеют концепцию выгружаемой памяти? Сколько времени это будет стоить? – Mikeage 16 April 2009 в 18:56
-
4Это не ответ. Ваше решение совершенно нереально во всех приложениях реального мира и называет его «компромиссным». неискренен. Ваша мифическая система, которая имеет 16 ГБ оперативной памяти, чтобы посвятить одну функцию, просто не существует. Вы бы также ответили «использовать квантовый компьютер». – Brian 16 April 2009 в 19:08
-
5Жертвенная память для скорости? Таблица 4GB + lookup никогда не будет вписываться в кеш на любой существующей машине, поэтому я бы предположил, что это, вероятно, медленнее, чем почти все другие ответы здесь. – Dan 14 January 2011 в 19:34
Почему бы не использовать встроенные ffs?
ffs (3) - справочная страница Linux Имя ffs - найти первый бит, заданный словом Synopsis#include <strings.h>
int ffs(int i);
#define _GNU_SOURCE
#include <string.h>
int ffsl(long int i);
int ffsll(long long int i);
Описание ffs () возвращает позицию первого (наименее значимого) бита, установленного в слове i. Меньшим значащим разрядом является позиция 1 и наиболее значимое положение, например. 32 или 64. Функции ffsll () и ffsl () делают то же самое, но принимают аргументы, возможно, разных размеров. Возвращаемое значение Эти функции возвращают позицию первого битового набора или 0, если в i не установлены биты. Соответствует 4.3BSD, POSIX.1-2001. Примечания. Системы BSD имеют прототип в <string.h>. -
1
Найден этот умный трюк с использованием «волшебных масок» в «Искусство программирования, часть 4», который делает это в O (log (n)) времени для n-разрядного числа. [с логическим (n) дополнительным пространством]. Типичные проверки решений для установленного бита - это O (n) или O (n) дополнительное пространство для таблицы поиска, поэтому это хороший компромисс.
Магические маски:
m0 = (...............01010101)
m1 = (...............00110011)
m2 = (...............00001111)
m3 = (.......0000000011111111)
....
Основная идея: нет конечных нулей в x = 1 * [(x & amp; m0) = 0] + 2 * [(x & amp; m1) = 0] + 4 * [(x & amp; m2) = 0] + ...
int lastSetBitPos(const uint64_t x) {
if (x == 0) return -1;
//For 64 bit number, log2(64)-1, ie; 5 masks needed
int steps = log2(sizeof(x) * 8); assert(steps == 6);
//magic masks
uint64_t m[] = { 0x5555555555555555, // .... 010101
0x3333333333333333, // .....110011
0x0f0f0f0f0f0f0f0f, // ...00001111
0x00ff00ff00ff00ff, //0000000011111111
0x0000ffff0000ffff,
0x00000000ffffffff };
//Firstly extract only the last set bit
uint64_t y = x & -x;
int trailZeros = 0, i = 0 , factor = 0;
while (i < steps) {
factor = ((y & m[i]) == 0 ) ? 1 : 0;
trailZeros += factor * pow(2,i);
++i;
}
return (trailZeros+1);
}
У OMG это просто спирально.
В большинстве этих примеров мало понимания о том, как работает все оборудование.
В любое время, когда у вас есть ветка, процессор должен угадайте, какая ветвь будет взята. Трубка инструкции загружается инструкциями, которые ведут вниз по угаданному пути. Если ЦП догадался неправильно, тогда заголовок команды загорается, а другая ветвь должна быть загружена.
Рассмотрим простой цикл while сверху. Предполагается, что он останется внутри цикла. Это будет неправильно, по крайней мере, один раз, когда он покинет цикл. Это WILL очистит инструкцию. Такое поведение немного лучше, чем угадать, что он покинет цикл, и в этом случае он будет промывать канал команд на каждой итерации.
Количество потерянных циклов процессора сильно отличается от одного типа процессора к другому. Но вы можете ожидать от 20 до 150 потерянных циклов процессора.
Следующая худшая группа - это то, где вы думаете, что собираетесь сохранить несколько итераций, разделив значение на более мелкие куски и добавив еще несколько ветвей. Каждая из этих ветвей добавляет дополнительную возможность сбросить трубку команд и стоить еще 20 - 150 тактов.
Давайте рассмотрим, что происходит, когда вы просматриваете значение в таблице. Скорее всего, в настоящее время значение не находится в кеше, по крайней мере, не в первый раз, когда вы вызываете свою функцию. Это означает, что CPU останавливается, пока значение загружается из кеша. Опять же это меняется от одной машины к другой. Новые чипы Intel фактически используют это как возможность обмена потоками, пока текущий поток ожидает завершения загрузки кеша. Это может быть легко дороже, чем сбой команды, но если вы выполняете эту операцию несколько раз, это может произойти только один раз.
Очевидно, что самым быстрым решением постоянного времени является решение, которое включает детерминированную математику , Чистое и элегантное решение.
Приносим извинения, если это уже было рассмотрено.
Каждый компилятор, который я использую, кроме XCODE AFAIK, имеет встроенные компиляторы как для прямого бита, так и для обратного бита. Они будут скомпилированы для одной команды сборки на большинстве аппаратных средств без Cache Miss, no Branch Miss-Prediction и других программистов, генерирующих блоки преткновения.
Для компиляторов Microsoft используют _BitScanForward & amp; _BitScanReverse. Для использования GCC __builtin_ffs, __builtin_clz, __builtin_ctz.
Кроме того, пожалуйста, воздержитесь от публикации ответа и потенциально обманчивых новичков, если вы недостаточно осведомлены о предмете обсуждения.
Извините, я полностью забыл предоставить решение .. Это код, который я использую в IPAD, который не имеет инструкции для уровня сборки для задачи:
unsigned BitScanLow_BranchFree(unsigned value)
{
bool bwl = (value & 0x0000ffff) == 0;
unsigned I1 = (bwl * 15);
value = (value >> I1) & 0x0000ffff;
bool bbl = (value & 0x00ff00ff) == 0;
unsigned I2 = (bbl * 7);
value = (value >> I2) & 0x00ff00ff;
bool bnl = (value & 0x0f0f0f0f) == 0;
unsigned I3 = (bnl * 3);
value = (value >> I3) & 0x0f0f0f0f;
bool bsl = (value & 0x33333333) == 0;
unsigned I4 = (bsl * 1);
value = (value >> I4) & 0x33333333;
unsigned result = value + I1 + I2 + I3 + I4 - 1;
return result;
}
. Здесь нужно понять, что это не сравнение, которое дорогая, но ветка, которая возникает после сравнения. Сравнение в этом случае вынуждается значением 0 или 1 с символом .. == 0, и результат используется для объединения математики, которая произошла бы по обе стороны от ветви.
Изменить :
Вышеприведенный код полностью нарушен. Этот код работает и остается без ветвей (если оптимизирован):
int BitScanLow_BranchFree(ui value)
{
int i16 = !(value & 0xffff) << 4;
value >>= i16;
int i8 = !(value & 0xff) << 3;
value >>= i8;
int i4 = !(value & 0xf) << 2;
value >>= i4;
int i2 = !(value & 0x3) << 1;
value >>= i2;
int i1 = !(value & 0x1);
int i0 = (value >> i1) & 1? 0 : -32;
return i16 + i8 + i4 + i2 + i1 + i0;
}
Это возвращает -1, если задано 0. Если вам все равно 0 или счастливы получить 31 для 0, удалите расчет i0, экономя кусок времени.
-
1
-
2
-
3Как вы можете назвать это «без ветвей»? когда он включает в себя тройной оператор? – BoltBait 22 February 2016 в 21:26
-
4Его условный ход. Единая инструкция языка ассемблера, которая принимает как возможные значения в качестве параметров, так и выполняет операцию mov, основанную на оценке условного выражения. И, таким образом, это «Свободная ветвь». нет перехода на другой неизвестный или, возможно, неправильный адрес. – Dan 17 March 2016 в 01:35
В соответствии с шахматной версией страницы BitScan и моими собственными измерениями вычесть и xor быстрее, чем negate и mask.
(Обратите внимание, что если вы собираетесь подсчитать конечные нули в 0, метод, поскольку у меня он возвращает 63, тогда как отрицание и маска возвращаются 0.)
Вот 64-битный вычитание и xor:
unsigned long v; // find the number of trailing zeros in 64-bit v
int r; // result goes here
static const int MultiplyDeBruijnBitPosition[64] =
{
0, 47, 1, 56, 48, 27, 2, 60, 57, 49, 41, 37, 28, 16, 3, 61,
54, 58, 35, 52, 50, 42, 21, 44, 38, 32, 29, 23, 17, 11, 4, 62,
46, 55, 26, 59, 40, 36, 15, 53, 34, 51, 20, 43, 31, 22, 10, 45,
25, 39, 14, 33, 19, 30, 9, 24, 13, 18, 8, 12, 7, 6, 5, 63
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v ^ (v-1)) * 0x03F79D71B4CB0A89U)) >> 58];
Для справки, вот 64-битная версия метода отрицания и маски:
unsigned long v; // find the number of trailing zeros in 64-bit v
int r; // result goes here
static const int MultiplyDeBruijnBitPosition[64] =
{
0, 1, 48, 2, 57, 49, 28, 3, 61, 58, 50, 42, 38, 29, 17, 4,
62, 55, 59, 36, 53, 51, 43, 22, 45, 39, 33, 30, 24, 18, 12, 5,
63, 47, 56, 27, 60, 41, 37, 16, 54, 35, 52, 21, 44, 32, 23, 11,
46, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x03F79D71B4CB0A89U)) >> 58];
-
1Это (v ^ (v-1)) работает v != 0. В случае v == 0 он возвращает 0xFF .... FF, в то время как (v & -v) дает нуль (что, кстати, тоже неверно, buf, по крайней мере, приводит к разумному результату). – CiaPan 12 June 2014 в 12:37
-
2@CiaPan: Это хороший момент, я упомянул об этом. Я предполагаю, что существует другое число Де Бройна, которое разрешило бы это, поставив 0 в 63-й индекс. – jnm2 12 June 2014 в 12:54
-
3Дух, это не проблема. 0 и 0x8000000000000000 оба результата приводят к 0xFFFFFFFFFFFFFFFF после v ^ (v-1), поэтому их не сообщают. В моем случае нуль никогда не будет введен. – jnm2 12 June 2014 в 18:13
Существует инструкция сборки x86 ( bsf ), которая сделает это. :)
Больше оптимизировано?!
Боковое примечание:
Оптимизация на этом уровне по своей природе зависит от архитектуры. Сегодняшние процессоры слишком сложны (с точки зрения предсказания ветвлений, промахов кэш-памяти, конвейерной обработки), что так сложно предсказать, какой код выполняется быстрее, на какой архитектуре. Уменьшение операций с 32 до 9 или подобное может даже снизить производительность на некоторых архитектурах. Оптимизированный код в одной архитектуре может привести к ухудшению кода в другом. Я думаю, вы бы либо оптимизировали это для конкретного процессора, либо оставили его таким, каким он есть, и пусть компилятор выбирает то, что, по его мнению, лучше.
-
1
-
2@dwc: Я понимаю, но я думаю, что этот пункт: «Любые идеи о том, как выжать из него некоторые циклы» & quot; делает такой ответ совершенно приемлемым! – Mehrdad Afshari 16 April 2009 в 18:08
-
3+1 Его ответ обязательно зависит от его архитектуры из-за сущности, поэтому опускаться до инструкций по сборке является вполне правильным ответом. – Chris Lutz 16 April 2009 в 18:10
-
4+1 Умный ответ, да, это не C или C ++, но это правильный инструмент для работы. – Andrew Hare 16 April 2009 в 18:12
-
5@Bastian: они устанавливают ZF = 1, если операнд равен нулю. – Mehrdad Afshari 16 April 2009 в 21:31
Большинство современных архитектур будут иметь некоторую инструкцию для поиска положения младшего бита набора или самого старшего бита или подсчета числа ведущих нулей и т. д.
Если у вас есть одна инструкция этого
Потратьте немного времени на то, чтобы работать над ним на бумаге, и понимаете, что x & (x-1) очистит младший бит набора в x, а ( x & ~(x-1) ) вернет только самый младший бит набора , независимо от архитектуры, длины слова и т. д. Зная это, тривиально использовать аппаратное число count-leading-zeroes / maximum-set-bit для поиска младшего бита набора, если нет явной инструкции для этого.
Если не существует соответствующей аппаратной поддержки вообще, реализованная здесь многократная и нулевая реализация приведенных здесь отсчетов количества отсчетов или одна из них на странице бит Twiddling Hacks можно тривиально преобразовать, чтобы дать минимальный бит бит, используя вышеприведенную идентичности и имеет то преимущество, что он является бесконтактным.
Другой метод (разделение по модулю и поиск) заслуживает особого упоминания здесь из той же ссылки, предоставленной @ anton-tykhyy. этот метод очень похож по эффективности на метод умножения и поиска DeBruijn с небольшим, но важным различием.
модуляция и поиск
unsigned int v; // find the number of trailing zeros in v
int r; // put the result in r
static const int Mod37BitPosition[] = // map a bit value mod 37 to its position
{
32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4,
7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5,
20, 8, 19, 18
};
r = Mod37BitPosition[(-v & v) % 37];
модуль модуляции и метод поиска возвращают разные значения для v = 0x00000000 и v = FFFFFFFF, тогда как метод умножения и поиска DeBruijn возвращает ноль на обоих входах.
test: -
unsigned int n1=0x00000000, n2=0xFFFFFFFF;
MultiplyDeBruijnBitPosition[((unsigned int )((n1 & -n1) * 0x077CB531U)) >> 27]); /* returns 0 */
MultiplyDeBruijnBitPosition[((unsigned int )((n2 & -n2) * 0x077CB531U)) >> 27]); /* returns 0 */
Mod37BitPosition[(((-(n1) & (n1))) % 37)]); /* returns 32 */
Mod37BitPosition[(((-(n2) & (n2))) % 37)]); /* returns 0 */
-
1
modмедленный. Вместо этого вы можете использовать оригинальный метод умножения и поиска и вычесть! Vизrдля обработки случаев краев. – Eitan T 11 July 2013 в 23:41 -
2@EitanT оптимизатор может хорошо преобразовать этот мод в быстрое умножение, как в восторге от хакеров – phuclv 12 June 2014 в 07:05
Это относится к @Anton Tykhyy answer
Вот моя реализация C ++ 11 constexpr, устраняющая броски и удаление предупреждения на VC ++ 17 путем обрезания 64-битного результата до 32 бит:
constexpr uint32_t DeBruijnSequence[32] =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
constexpr uint32_t ffs ( uint32_t value )
{
return DeBruijnSequence[
(( ( value & ( -static_cast<int32_t>(value) ) ) * 0x077CB531ULL ) & 0xFFFFFFFF)
>> 27];
}
Чтобы обойти проблему 0x1 и 0x0, возвращающих 0, вы можете сделать:
constexpr uint32_t ffs ( uint32_t value )
{
return (!value) ? 32 : DeBruijnSequence[
(( ( value & ( -static_cast<int32_t>(value) ) ) * 0x077CB531ULL ) & 0xFFFFFFFF)
>> 27];
}
, но если компилятор не может или не будет препрограммировать вызов он добавит пару циклов к вычислению.
Наконец, если интересно, вот список статических утверждений, чтобы проверить, что код выполняет то, что предназначено для:
static_assert (ffs(0x1) == 0, "Find First Bit Set Failure.");
static_assert (ffs(0x2) == 1, "Find First Bit Set Failure.");
static_assert (ffs(0x4) == 2, "Find First Bit Set Failure.");
static_assert (ffs(0x8) == 3, "Find First Bit Set Failure.");
static_assert (ffs(0x10) == 4, "Find First Bit Set Failure.");
static_assert (ffs(0x20) == 5, "Find First Bit Set Failure.");
static_assert (ffs(0x40) == 6, "Find First Bit Set Failure.");
static_assert (ffs(0x80) == 7, "Find First Bit Set Failure.");
static_assert (ffs(0x100) == 8, "Find First Bit Set Failure.");
static_assert (ffs(0x200) == 9, "Find First Bit Set Failure.");
static_assert (ffs(0x400) == 10, "Find First Bit Set Failure.");
static_assert (ffs(0x800) == 11, "Find First Bit Set Failure.");
static_assert (ffs(0x1000) == 12, "Find First Bit Set Failure.");
static_assert (ffs(0x2000) == 13, "Find First Bit Set Failure.");
static_assert (ffs(0x4000) == 14, "Find First Bit Set Failure.");
static_assert (ffs(0x8000) == 15, "Find First Bit Set Failure.");
static_assert (ffs(0x10000) == 16, "Find First Bit Set Failure.");
static_assert (ffs(0x20000) == 17, "Find First Bit Set Failure.");
static_assert (ffs(0x40000) == 18, "Find First Bit Set Failure.");
static_assert (ffs(0x80000) == 19, "Find First Bit Set Failure.");
static_assert (ffs(0x100000) == 20, "Find First Bit Set Failure.");
static_assert (ffs(0x200000) == 21, "Find First Bit Set Failure.");
static_assert (ffs(0x400000) == 22, "Find First Bit Set Failure.");
static_assert (ffs(0x800000) == 23, "Find First Bit Set Failure.");
static_assert (ffs(0x1000000) == 24, "Find First Bit Set Failure.");
static_assert (ffs(0x2000000) == 25, "Find First Bit Set Failure.");
static_assert (ffs(0x4000000) == 26, "Find First Bit Set Failure.");
static_assert (ffs(0x8000000) == 27, "Find First Bit Set Failure.");
static_assert (ffs(0x10000000) == 28, "Find First Bit Set Failure.");
static_assert (ffs(0x20000000) == 29, "Find First Bit Set Failure.");
static_assert (ffs(0x40000000) == 30, "Find First Bit Set Failure.");
static_assert (ffs(0x80000000) == 31, "Find First Bit Set Failure.");
Если C ++ 11 доступен для вас, компилятор иногда может выполнить задачу для вас:)
constexpr std::uint64_t lssb(const std::uint64_t value)
{
return !value ? 0 : (value % 2 ? 1 : lssb(value >> 1) + 1);
}
Результат - это индекс на основе 1.
-
1Умный, но он компилируется в катастрофически плохую сборку, когда вход не является константой времени компиляции. [D0] godbolt.org/g/7ajMyT . (Немой петля над битами с gcc или вызов фактической рекурсивной функции с clang.) Gcc / clang может оценивать ffs() во время компиляции, поэтому вам не нужно использовать это для непрерывного распространения для работы. (Конечно, вам нужно избегать inline-asm.) Если вам действительно нужно что-то, что работает как C ++ 11 constexpr, вы все равно можете использовать GNU C __builtin_ffs. – Peter Cordes 3 August 2017 в 12:26
Недавно я вижу, что премьер-министр Сингапура опубликовал программу, которую он написал на facebook, есть одна строка, чтобы упомянуть ее.
Логика - это просто «значение & amp; -значение», предположим, что у вас есть 0x0FF0, затем 0FF0 & amp; (F00F + 1), что равно 0x0010, что означает, что самый низкий 1 находится в 4-м бите ..:)
-
1Это изолирует младший бит, но не дает вам своей позиции, о которой спрашивает этот вопрос. – rhashimoto 31 May 2015 в 17:14
-
2
-
3
-
4Упс, у меня все плохо. Я принял минус за тильду. игнорировать мой комментарий – khw 13 January 2018 в 07:04
Вот одна простая альтернатива, хотя поиск журналов является довольно дорогостоящим.
if(n == 0)
return 0;
return log2(n & -n)+1; //Assuming the bit index starts from 1
Почему бы не использовать бинарный поиск? Это всегда будет завершено после 5 операций (при условии, что размер int равен 4 байтам):
if (0x0000FFFF & value) {
if (0x000000FF & value) {
if (0x0000000F & value) {
if (0x00000003 & value) {
if (0x00000001 & value) {
return 1;
} else {
return 2;
}
} else {
if (0x0000004 & value) {
return 3;
} else {
return 4;
}
}
} else { ...
} else { ...
} else { ...
-
1+1 Это очень похоже на мой ответ. Лучшее время выполнения кода хуже, чем мое предложение, но самое худшее время выполнения - лучше. – Brian R. Bondy 16 April 2009 в 19:24