설정된 최하위 비트의 위치 사소한 구현은 다음과 같습니다. unsigned

정수로 설정된 최하위 비트의 위치를 ​​결정하는 효율적인 방법을 찾고 있습니다. 예를 들어 0x0FF0의 경우 4가됩니다.

사소한 구현은 다음과 같습니다.

unsigned GetLowestBitPos(unsigned value)
{
   assert(value != 0); // handled separately

   unsigned pos = 0;
   while (!(value & 1))
   {
      value >>= 1;
      ++pos;
   }
   return pos;
}

그것에서 일부 사이클을 짜내는 방법에 대한 아이디어가 있습니까?

(참고 :이 질문은 사람들이 xyzoptimization이 나쁘다고 말하는 것이 아니라 그러한 것을 즐기는 사람들을위한 것입니다.)

[편집] 아이디어 주셔서 감사합니다 모두! 나는 다른 몇 가지도 배웠다. 멋있는!

답변

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];

유용한 참조 :

답변

내장 된 ffs를 사용하지 않는 이유는 무엇 입니까? (저는 Linux에서 man 페이지를 가져 왔지만 그보다 더 널리 사용 가능합니다.)

ffs (3)-Linux man 페이지

이름

ffs-단어에서 첫 번째 비트 세트 찾기

개요

#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 () 함수는 동일한 작업을 수행하지만 크기가 다른 인수를 사용합니다.

반환 값

이 함수는 첫 번째 비트 세트의 위치를 ​​반환하거나 i에 비트가 설정되지 않은 경우 0을 반환합니다.

준수

4.3BSD, POSIX.1-2001.

노트

BSD 시스템은 <string.h>.

답변

이를 수행하는 x86 어셈블리 명령 ( bsf)이 있습니다. 🙂

더 최적화?!

참고 :

이 수준에서의 최적화는 본질적으로 아키텍처에 따라 다릅니다. 오늘날의 프로세서는 너무 복잡하여 (분기 예측, 캐시 미스, 파이프 라이닝 측면에서) 어떤 코드가 어떤 아키텍처에서 더 빨리 실행되는지 예측하기가 너무 어렵습니다. 작업을 32에서 9로 줄이면 일부 아키텍처에서는 성능이 저하 될 수도 있습니다. 단일 아키텍처에서 최적화 된 코드는 다른 아키텍처에서 더 나쁜 코드를 초래할 수 있습니다. 특정 CPU에 대해이를 최적화하거나 그대로두고 컴파일러가 더 낫다고 생각하는 것을 선택하도록 할 것이라고 생각합니다.

답변

대부분의 최신 아키텍처에는 가장 낮은 세트 비트 또는 가장 높은 세트 비트의 위치를 ​​찾거나 선행 0의 수를 계산하는 등의 지침이 있습니다.

이 클래스의 명령어가 하나라도 있으면 다른 명령어를 저렴하게 에뮬레이션 할 수 있습니다.

잠시 시간을내어 종이로 작업 x & (x-1)하고 x에서 가장 낮은 세트 비트를 지우고 ( x & ~(x-1) )구조, 단어 길이 등에 관계없이 가장 낮은 세트 비트 만 반환 할 것임을 깨달으십시오 .이 사실을 알면 하드웨어 카운트 리더를 사용하는 것은 간단합니다. -zeroes / high-set-bit는 명시적인 명령이없는 경우 가장 낮은 세트 비트를 찾습니다.

관련 하드웨어 지원이 전혀없는 경우 여기에 제공된 카운트 선행 0의 곱셈 및 조회 구현 또는 Bit Twiddling Hacks 페이지 에있는 것 중 하나 는 위의 ID를 사용하여 가장 낮은 세트 비트를 제공하도록 간단 하게 변환 할 수 있습니다. 분기가 없다는 장점이 있습니다.

답변

Weee, 많은 솔루션이 있지만 벤치 마크가 아닙니다. 당신은 사람들이 당신 자신을 부끄러워해야합니다 😉

내 컴퓨터는 Windows 7 64 비트를 실행하는 Intel i530 (2.9GHz)입니다. 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);
}

답변

이에 대한 가장 빠른 (비 내장 / 비 어셈블러) 솔루션은 가장 낮은 바이트를 찾은 다음 256 항목 조회 테이블에서 해당 바이트를 사용하는 것입니다. 이것은 4 개의 조건부 명령어와 최상의 경우 1의 최악의 경우 성능을 제공합니다. 이것은 가장 적은 양의 명령어 일뿐만 아니라 최신 하드웨어에서 매우 중요한 분기의 양이 가장 적다는 것입니다.

테이블 (256 개의 8 비트 항목)에는 0-255 범위의 각 숫자에 대한 LSB의 인덱스가 포함되어야합니다. 값의 각 바이트를 확인하고 0이 아닌 가장 낮은 바이트를 찾은 다음이 값을 사용하여 실제 인덱스를 조회합니다.

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;
}

답변

OMG는 이것이 방금 나선형을 이루었습니다.

이러한 예제 중 대부분이 부족한 것은 모든 하드웨어가 어떻게 작동하는지에 대한 약간의 이해입니다.

분기가있을 때마다 CPU는 어떤 분기를 사용할지 추측해야합니다. 명령 파이프에는 추측 된 경로를 안내하는 명령이로드됩니다. CPU가 잘못 추측 한 경우 명령 파이프가 플러시되고 다른 분기를로드해야합니다.

상단의 간단한 while 루프를 고려하십시오. 추측은 루프 내에 머무르는 것입니다. 루프를 떠날 때 적어도 한 번은 잘못됩니다. 이것은 명령 파이프를 플러시합니다. 이 동작은 루프를 떠날 것이라고 추측하는 것보다 약간 낫습니다.이 경우 모든 반복에서 명령 파이프를 플러시합니다.

손실되는 CPU주기의 양은 프로세서 유형에 따라 크게 다릅니다. 그러나 20 ~ 150 개의 CPU 손실주기를 예상 할 수 있습니다.

다음으로 더 나쁜 그룹은 값을 작은 조각으로 나누고 몇 개의 분기를 더 추가하여 몇 번의 반복을 절약 할 것이라고 생각하는 곳입니다. 이러한 각 분기는 명령 파이프를 플러시 할 수있는 추가 기회를 추가하고 추가로 20 ~ 150 클럭 사이클을 소모합니다.

테이블에서 값을 조회 할 때 어떤 일이 발생하는지 생각해 보겠습니다. 적어도 함수가 처음 호출 될 때는 값이 현재 캐시에 없을 가능성이 있습니다. 이는 값이 캐시에서로드되는 동안 CPU가 중단됨을 의미합니다. 다시 말하지만 이것은 기계마다 다릅니다. 새로운 Intel 칩은 실제로 이것을 현재 스레드가 캐시로드가 완료되기를 기다리는 동안 스레드를 교환 할 수있는 기회로 사용합니다. 이것은 명령 파이프 플러시보다 비용이 많이들 수 있지만이 작업을 여러 번 수행하는 경우 한 번만 발생할 가능성이 높습니다.

분명히 가장 빠른 상수 시간 솔루션은 결정 론적 수학을 포함하는 솔루션입니다. 순수하고 우아한 솔루션.

이것이 이미 다루어 졌다면 사과드립니다.

XCODE AFAIK를 제외하고 내가 사용하는 모든 컴파일러에는 순방향 비트 스캔과 역방향 비트 스캔 모두에 대한 컴파일러 내장 함수가 있습니다. 이들은 대부분의 하드웨어에서 캐시 미스, 분기 미스 예측 및 다른 프로그래머 생성 걸림돌이없는 단일 어셈블리 명령어로 컴파일됩니다.

Microsoft 컴파일러의 경우 _BitScanForward 및 _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과 함께 0 또는 1의 값으로 강제되며 그 결과는 분기의 양쪽에서 발생했을 수있는 수학을 결합하는 데 사용됩니다.

편집하다:

위의 코드는 완전히 손상되었습니다. 이 코드는 작동하며 여전히 분기가 없습니다 (최적화 된 경우).

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;
}

0이 주어지면 -1을 반환합니다. 0에 대해 신경 쓰지 않거나 0에 대해 31을 얻고 싶다면 i0 계산을 제거하여 시간을 절약하십시오.