长整数中的单个位的索引(以C为单位) [英] Index of single bit in long integer (in C)

问题描述

我正在尝试寻找一种最佳代码，以便在长整数(64位)中定位单个位索引.长整数恰好具有一个置1的位.(使用C语言)

I am trying to find an optimal code to locate a single bit index in a long integer (64 bit). The long integer has exactly one set bit. (Using C language)

当前，我只是将整个内容移位一位，然后检查零.我已经阅读了有关查找表的信息，但是对于整个64位而言，它是无效的.我考虑过要检查每个8位是否为零，如果不使用查找的话，但是我仍然必须一次移动8位.(移动8胜过移动8倍?)

Currently, I am just shifting the whole thing by one bit, then checking for zero. I have read about lookup tables, but it won't do for the whole 64 bits. I thought about checking each 8 bits for zero, if not use a lookup, but still I'll have to shift by 8 at a time. (Shifting by 8 is better than shifting by one 8 times?)

(注意:我正在为移动设备开发，并且它们[缓慢地]变慢).

(Note: I am developing for mobile devices, and they are [not surprisingly] slow).

推荐答案

每当我需要某种方式来操作位时，我总是会寻找

Whenever I need some way to manipulate bits, I always look for Bit Twiddling Hacks. It has few solutions for your problem as well.

该解决方案似乎是最快，最先进的:

This solution seems to be fast and most advanced:

并行计算右侧连续的零位(尾数)

Count the consecutive zero bits (trailing) on the right in parallel

unsigned int v;      // 32-bit word input to count zero bits on right
unsigned int c = 32; // c will be the number of zero bits on the right
v &= -signed(v);
if (v) c--;
if (v & 0x0000FFFF) c -= 16;
if (v & 0x00FF00FF) c -= 8;
if (v & 0x0F0F0F0F) c -= 4;
if (v & 0x33333333) c -= 2;
if (v & 0x55555555) c -= 1;

对于N位字，操作数最多为3 * lg(N)+ 4.

The number of operations is at most 3 * lg(N) + 4, roughly, for N bit words.

这篇关于长整数中的单个位的索引(以C为单位)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！