비트 배열에 설정된 최상위 비트(맨 왼쪽) 찾기
0번째 인덱스는 배열의 첫 번째 바이트의 MSB이고, 8번째 인덱스는 두 번째 바이트의 MSB인 비트 배열 구현 등이 있습니다.
이 비트 배열에 설정된 첫 번째 비트를 찾는 빠른 방법은 무엇입니까?제가 찾아본 모든 관련 솔루션은 처음에 가장 중요하지 않은 부분을 찾지만, 저는 첫 번째 가장 중요한 부분이 필요합니다.그래서 0x00A1이 주어지면 8을 원합니다(왼쪽에서 9번째 비트이므로).
GCC는 x86/x64의 BSR, ARM의 CLZ 등으로 변환하여 하드웨어가 구현하지 않으면 명령을 에뮬레이트합니다.
Visual C++ 2005 이상 버전은 .
tl:dr; 32비트의 경우 de Bruijn 곱셈을 사용합니다.
이것은 가장 빠른 휴대용 알고리즘입니다.이 스레드의 다른 모든 휴대용 32비트 MSB 알고리즘보다 훨씬 빠르고 정확합니다.
또한 de Bruijn 알고리즘은 입력이 0일 때 올바른 결과를 반환합니다.__builtin_clz 및 _BitScanReverse 명령은 입력이 0이면 잘못된 결과를 반환합니다.
윈도우즈 x86-64에서 de Bruijn 곱셈은 성능 차이가 약 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];
}
이 스레드의 다른 모든 답변은 작성자가 제안하는 것보다 훨씬 더 잘못 실행되거나 결과를 올바르게 계산하지 않거나 둘 다 수행되지 않습니다.이 모든 것을 벤치마킹하고, 그들이 주장하는 바를 수행하는지 확인해 보겠습니다.
다음은 이러한 모든 구현을 테스트하기 위한 간단한 C++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
"성능 정크"와 마이크로소프트 네이티브 구현은 입력이 0일 때 서로 다른 작업을 수행합니다. msbPerformanceJunkie32는 -1을 생성하고 마이크로소프트의 _BitScanReverse는 기본 하드웨어 명령과 일치하는 임의의 숫자를 생성합니다.또한 msb PerformanceJunkie32 구현은 다른 모든 답변에서 하나씩 차이가 나는 결과를 생성합니다.
다음은 릴리스 모드에서 컴파일된 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 Brujn 버전은 분기가 없기 때문에 다른 구현보다 우수하며, 따라서 균일하게 분산된 출력 집합을 생성하는 입력에 대해 잘 실행됩니다.다른 모든 버전은 최신 CPU에 대한 분기 오예측의 페널티 때문에 임의 입력에 비해 느립니다.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
}
성능 중독자로서 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];
}
이를 위한 여러 가지 방법이 있으며, 여러 구현의 상대적인 성능은 어느 정도 기계에 의존합니다(비슷한 목적으로 어느 정도 벤치마킹한 적이 있습니다).일부 컴퓨터에는 이를 위한 기본 제공 지침도 있습니다(가능하고 휴대성을 처리할 수 있는 경우 하나 사용).
여기에서 일부 구현을 확인하십시오("정수 로그 기반 2" 참조).만약 당신이 GCC를 사용한다면, 기능들을 참조하십시오.__builtin_clz그리고.__builtin_clzl(각각 0이 아닌 부호 없는 int와 부호 없는 long에 대해 이 작업을 수행합니다.)"clz"는 "count leading zero"를 의미하며, 이는 동일한 문제를 설명하는 또 다른 방법입니다.
물론 비트 배열이 적합한 기계어에 맞지 않는 경우 배열에서 단어 위에 반복하여 0이 아닌 첫 번째 단어를 찾은 다음 해당 단어에 대해서만 이 계산을 수행해야 합니다.
가장 빠른 방법은 BSR(비트 스캔 역방향) x86 명령을 참조하십시오.: 인텔 문서: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 #IntegerLogOvible
저는 가장 중요한 비트를 얻기 위해 많은 기능을 사용했지만, 일반적으로 32비트와 64비트 사이를 이동하거나 x86_64와 x86 상자 사이를 이동하는 문제가 발생합니다. »__builtin_clz,__builtin_clzl그리고.__builtin_clzll32/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 charunsigned 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배 정도 더 빠릅니다.
x86을 사용하는 경우, (gcc 월드에서) 가장 낮은 비트는 "ffs", 가장 높은 비트는 "fls"로 발음되는 find-first-bit 명령어와 결합하여 SSE2 연산을 사용하여 거의 모든 바이트별 또는 워드별 솔루션을 이길 수 있습니다.답변에서 "C" 코드를 포맷하는 데 문제가 있어 죄송합니다. 확인하십시오. http://mischasan.wordpress.com/2011/11/03/sse2-bit-trick-ffsfls-for-xmm-registers/
x86에는 비트 인덱스를 반환하는 BSR 명령어가 있습니다.
하지만 안타깝게도 모든 컴파일러에 효율적으로 노출되는 휴대용 내장물은 없습니다. GNU C는__builtin_clz,그렇지만unsigned bitidx = 31 - __builtin_clz(x);현재 GCC 및 ICC에서는 BSR만 최적화하지 않습니다. (식이 동일하므로 가능하다는 것을 증명하는 clang을 사용합니다.)
은 다은다을다니정합의를 정의합니다.BSR32()그리고.BSR64()효율적으로 컴파일할 수 있는 매크로 또는 함수bsrx86에 대한 명령입니다. (입력이 0인 경우 가비지 결과를 생성합니다.input input=0을 할 수 있는
비 x86으로의 이동성은 다음과 같은 추가적인 작업이 필요합니다.31-__builtin_clz대부분의 비 x86 ISA는 선행 0 비트 스캔이 있는 경우 비트 인덱스 대신 선행 0을 카운트합니다. C가 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빌트인은 LSB의 비트 인덱스, 즉 후행 0의 수를 반환하는 명령어의 동작과 일치하기 때문에 컴파일러에 많은 도움이 필요하지 않을 것입니다.
콜러 테트자출호unsigned test32(unsigned x) { return BSR32(x); }는 모든 주요 x86 컴파일러, Godbolt 컴파일러 탐색기에서 1개의 명령어로, BSR64는 64비트 피연산자 크기 버전으로 동일한 방식으로 인라인됩니다.참고 항목가장 중요한 비트 아래의 모든 비트를 0으로 만드는 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는 단지clang은 BSR을, 다과같습다니서만음지받에만▁we다▁just같니▁cl습:▁but▁bcl.
# 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입력이 0인 경우. 결과에 따라 플래그를 설정하는 대부분의 명령과 달리 BSR은 입력에 따라 ZF를 설정합니다.)
와 함께-march=haswell(또는 BMI1 지침의 사용을 가능하게 하는 것), 그것은 나쁘지는 않지만 여전히 BSR만큼 좋지는 않습니다.모듈로 출력 종속성. 컴파일러는 주로 lzcnt에 대해 작동하지만 이상하게도 BSR에는 작동하지 않습니다. (여기서 출력 종속성은 input=0 동작 때문에 실제 종속성입니다.)LZCNT의 "출력 의존성"을 깨는 것이 왜 중요합니까?
순수한 C에서 이를 수행하는 가장 좋은 두 가지 방법:
먼저 바이트/워드 배열을 선형으로 검색하여 0이 아닌 첫 번째 바이트/워드를 찾은 다음 찾은 바이트/워드에 대해 2진수 검색을 수행합니다.
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는 로그2(8)) 조건부 점프를 통해 답을 얻습니다.최신 x86 컴퓨터에서는 마지막 컴퓨터가 조건부 이동에 최적화됩니다.
또는 룩업 테이블을 사용하여 바이트를 설정된 첫 번째 비트의 인덱스에 매핑합니다.
검색할 수 있는 관련 항목은 정수 로그2 함수입니다.제가 기억하기로는 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비트 숫자(부호가 없는 긴 길이)에서 작동합니다.또한 많은 사람들이 제가 몰랐던 내장된 g++ 기능을 지적했습니다.흥미롭군요.
어쨌든, 이것은 6번의 반복에서 가장 중요한 비트를 찾고 함수에 0을 전달하면 어사션을 제공합니다.칩셋에 대한 지침에 액세스할 수 있는 경우에는 사용하기에 가장 좋은 기능이 아닙니다.
또한 += 대신 |=을 사용합니다. 이는 항상 2의 거듭제곱이고 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's 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데이터의 크기 차이
음, 당신의 태그는 32비트를 나타내지만 당신이 사용하는 값은 16비트인 것 같습니다.32비트를 의미했다면 0x00a1에 대한 답은 8이 아니라 24가 되어야 한다고 생각합니다.
왼쪽에서 MSB 비트 인덱스를 찾고 있으며 unt32_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;
}
Java의 경우 다음을 사용합니다.
static public final int msb(int n) {
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
n >>>= 1;
n += 1;
return n;
}
그리고:
static public final int msb_index(int n) {
final int[] multiply_de_bruijn_bit_position = {
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
};
return multiply_de_bruijn_bit_position[(msb(n) * 0x077CB531) >>> 27];
}
#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; \
})
언급URL : https://stackoverflow.com/questions/2589096/find-most-significant-bit-left-most-that-is-set-in-a-bit-array
'sourcecode' 카테고리의 다른 글
| 최대 절전 모드에서 MySQL이 아닌 다른 표준 시간대를 사용하는 경우 날짜를 뺀 날짜를 저장/검색합니다. (0) | 2023.07.07 |
|---|---|
| 제공자 설치 관리자 모듈을 로드하지 못했습니다.허용 가능한 모듈을 찾을 수 없습니다.로컬 버전은 0이고 원격 버전은 0 오류 변동입니다. (0) | 2023.07.07 |
| GitHub 풀 요청을 Git로 확인하려면 어떻게 해야 합니까? (0) | 2023.07.07 |
| Java에서 Excel 워크북 간에 시트를 복사하는 방법 (0) | 2023.07.02 |
| 내부 순환; 빌드에서 신뢰할 수 없는 결과를 생성할 수 있음: Xcode 오류 (0) | 2023.07.02 |