整数的位反转,忽略整数大小和字节顺序
-
09-06-2019 - |
题
给定一个整数 typedef:
typedef unsigned int TYPE;
或者
typedef unsigned long TYPE;
我有以下代码来反转整数的位:
TYPE max_bit= (TYPE)-1;
void reverse_int_setup()
{
TYPE bits= (TYPE)max_bit;
while (bits <<= 1)
max_bit= bits;
}
TYPE reverse_int(TYPE arg)
{
TYPE bit_setter= 1, bit_tester= max_bit, result= 0;
for (result= 0; bit_tester; bit_tester>>= 1, bit_setter<<= 1)
if (arg & bit_tester)
result|= bit_setter;
return result;
}
只需要首先运行reverse_int_setup(),它存储一个最高位打开的整数,然后调用reverse_int(精氨酸) 返回 精氨酸 其位反转(用作二叉树的键,取自递增计数器,但这或多或少无关)。
在调用reverse_int_setup()之后,是否有一种与平台无关的方法可以在编译时获得正确的max_int值;否则,是否有您考虑的算法 更好/更精简 比我为reverse_int()准备的那个?
谢谢。
解决方案
#include<stdio.h>
#include<limits.h>
#define TYPE_BITS sizeof(TYPE)*CHAR_BIT
typedef unsigned long TYPE;
TYPE reverser(TYPE n)
{
TYPE nrev = 0, i, bit1, bit2;
int count;
for(i = 0; i < TYPE_BITS; i += 2)
{
/*In each iteration, we swap one bit on the 'right half'
of the number with another on the left half*/
count = TYPE_BITS - i - 1; /*this is used to find how many positions
to the left (and right) we gotta move
the bits in this iteration*/
bit1 = n & (1<<(i/2)); /*Extract 'right half' bit*/
bit1 <<= count; /*Shift it to where it belongs*/
bit2 = n & 1<<((i/2) + count); /*Find the 'left half' bit*/
bit2 >>= count; /*Place that bit in bit1's original position*/
nrev |= bit1; /*Now add the bits to the reversal result*/
nrev |= bit2;
}
return nrev;
}
int main()
{
TYPE n = 6;
printf("%lu", reverser(n));
return 0;
}
这次我使用了 TK 中的“位数”想法,但通过不假设一个字节包含 8 位而是使用 CHAR_BIT 宏,使其更加可移植。现在代码更加高效(删除了内部 for 循环)。我希望这次的代码也能稍微不那么神秘。:)
使用 count 的必要性在于,我们必须在每次迭代中移动一位的位置数量有所不同 - 我们必须将最右边的位移动 31 个位置(假设为 32 位数字),将第二个最右边的位移动 29 个位置,等等在。因此,随着 i 的增加,计数必须随着每次迭代而减少。
希望这些信息有助于理解代码......
其他提示
以下程序用于演示一种更精简的位反转算法,该算法可以轻松扩展以处理 64 位数字。
#include <stdio.h>
#include <stdint.h>
int main(int argc, char**argv)
{
int32_t x;
if ( argc != 2 )
{
printf("Usage: %s hexadecimal\n", argv[0]);
return 1;
}
sscanf(argv[1],"%x", &x);
/* swap every neigbouring bit */
x = (x&0xAAAAAAAA)>>1 | (x&0x55555555)<<1;
/* swap every 2 neighbouring bits */
x = (x&0xCCCCCCCC)>>2 | (x&0x33333333)<<2;
/* swap every 4 neighbouring bits */
x = (x&0xF0F0F0F0)>>4 | (x&0x0F0F0F0F)<<4;
/* swap every 8 neighbouring bits */
x = (x&0xFF00FF00)>>8 | (x&0x00FF00FF)<<8;
/* and so forth, for say, 32 bit int */
x = (x&0xFFFF0000)>>16 | (x&0x0000FFFF)<<16;
printf("0x%x\n",x);
return 0;
}
该代码不应包含错误,并使用 0x12345678 进行测试,生成 0x1e6a2c48,这是正确的答案。
typedef unsigned long TYPE;
TYPE reverser(TYPE n)
{
TYPE k = 1, nrev = 0, i, nrevbit1, nrevbit2;
int count;
for(i = 0; !i || (1 << i && (1 << i) != 1); i+=2)
{
/*In each iteration, we swap one bit
on the 'right half' of the number with another
on the left half*/
k = 1<<i; /*this is used to find how many positions
to the left (or right, for the other bit)
we gotta move the bits in this iteration*/
count = 0;
while(k << 1 && k << 1 != 1)
{
k <<= 1;
count++;
}
nrevbit1 = n & (1<<(i/2));
nrevbit1 <<= count;
nrevbit2 = n & 1<<((i/2) + count);
nrevbit2 >>= count;
nrev |= nrevbit1;
nrev |= nrevbit2;
}
return nrev;
}
这在 Windows 下的 gcc 中工作得很好,但我不确定它是否完全独立于平台。几个值得关注的地方是:
for 循环中的条件 - 它假设当您将 1 左移超出最左边的位时,您会得到 0 和 1 '脱落'(我所期望的以及旧的 Turbo C 给出的 iirc),或者1 绕一圈,你会得到 1 (这似乎是 gcc 的行为)。
内部 while 循环中的条件:往上看。但这里发生了一件奇怪的事情:在这种情况下,gcc似乎让1掉下来而不是绕圈!
该代码可能很神秘:如果您有兴趣并需要解释,请随时询问 - 我会将其放在某个地方。
@ΤΖΩΤΖΙΟΥ
为了回复 ΤΖΩΤΖIOY 的评论,我提出了上述的修改版本,该版本取决于位宽的上限。
#include <stdio.h>
#include <stdint.h>
typedef int32_t TYPE;
TYPE reverse(TYPE x, int bits)
{
TYPE m=~0;
switch(bits)
{
case 64:
x = (x&0xFFFFFFFF00000000&m)>>16 | (x&0x00000000FFFFFFFF&m)<<16;
case 32:
x = (x&0xFFFF0000FFFF0000&m)>>16 | (x&0x0000FFFF0000FFFF&m)<<16;
case 16:
x = (x&0xFF00FF00FF00FF00&m)>>8 | (x&0x00FF00FF00FF00FF&m)<<8;
case 8:
x = (x&0xF0F0F0F0F0F0F0F0&m)>>4 | (x&0x0F0F0F0F0F0F0F0F&m)<<4;
x = (x&0xCCCCCCCCCCCCCCCC&m)>>2 | (x&0x3333333333333333&m)<<2;
x = (x&0xAAAAAAAAAAAAAAAA&m)>>1 | (x&0x5555555555555555&m)<<1;
}
return x;
}
int main(int argc, char**argv)
{
TYPE x;
TYPE b = (TYPE)-1;
int bits;
if ( argc != 2 )
{
printf("Usage: %s hexadecimal\n", argv[0]);
return 1;
}
for(bits=1;b;b<<=1,bits++);
--bits;
printf("TYPE has %d bits\n", bits);
sscanf(argv[1],"%x", &x);
printf("0x%x\n",reverse(x, bits));
return 0;
}
笔记:
- gcc 将针对 64 位常量发出警告
- printfs 也会生成警告
- 如果您需要超过 64 位,代码应该足够简单以进行扩展
我为我在上面犯下的编码罪行提前道歉 - 仁慈的先生!
有一个很好的“Bit Twiddling Hacks”集合,包括各种用 C 语言编码的简单和不那么简单的位反转算法,位于 http://graphics.stanford.edu/~seander/bithacks.html.
我个人喜欢“显而易见”的算法(http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious)因为,这很明显。其他一些可能需要较少的指令来执行。如果我真的需要优化某些东西,我可能会选择不太明显但更快的版本。否则,出于可读性、可维护性和可移植性的考虑,我会选择“Obvious”。
这是一个更普遍有用的变体。它的优点是它能够在要反转的值的位长度(代码字)未知的情况下工作,但保证不会超过我们称为 maxLength 的值。这种情况的一个很好的例子是霍夫曼码解压缩。
下面的代码适用于长度为 1 到 24 位的码字。它已针对 Pentium D 上的快速执行进行了优化。请注意,每次使用它最多会访问查找表 3 次。我尝试了许多变体,将这个数字减少到 2,但代价是需要更大的表(4096 和 65,536 个条目)。这个带有 256 字节表的版本是明显的赢家,部分原因是表数据位于高速缓存中非常有利,或许还因为处理器具有 8 位表查找/翻译指令。
const unsigned char table[] = {
0x00,0x80,0x40,0xC0,0x20,0xA0,0x60,0xE0,0x10,0x90,0x50,0xD0,0x30,0xB0,0x70,0xF0,
0x08,0x88,0x48,0xC8,0x28,0xA8,0x68,0xE8,0x18,0x98,0x58,0xD8,0x38,0xB8,0x78,0xF8,
0x04,0x84,0x44,0xC4,0x24,0xA4,0x64,0xE4,0x14,0x94,0x54,0xD4,0x34,0xB4,0x74,0xF4,
0x0C,0x8C,0x4C,0xCC,0x2C,0xAC,0x6C,0xEC,0x1C,0x9C,0x5C,0xDC,0x3C,0xBC,0x7C,0xFC,
0x02,0x82,0x42,0xC2,0x22,0xA2,0x62,0xE2,0x12,0x92,0x52,0xD2,0x32,0xB2,0x72,0xF2,
0x0A,0x8A,0x4A,0xCA,0x2A,0xAA,0x6A,0xEA,0x1A,0x9A,0x5A,0xDA,0x3A,0xBA,0x7A,0xFA,
0x06,0x86,0x46,0xC6,0x26,0xA6,0x66,0xE6,0x16,0x96,0x56,0xD6,0x36,0xB6,0x76,0xF6,
0x0E,0x8E,0x4E,0xCE,0x2E,0xAE,0x6E,0xEE,0x1E,0x9E,0x5E,0xDE,0x3E,0xBE,0x7E,0xFE,
0x01,0x81,0x41,0xC1,0x21,0xA1,0x61,0xE1,0x11,0x91,0x51,0xD1,0x31,0xB1,0x71,0xF1,
0x09,0x89,0x49,0xC9,0x29,0xA9,0x69,0xE9,0x19,0x99,0x59,0xD9,0x39,0xB9,0x79,0xF9,
0x05,0x85,0x45,0xC5,0x25,0xA5,0x65,0xE5,0x15,0x95,0x55,0xD5,0x35,0xB5,0x75,0xF5,
0x0D,0x8D,0x4D,0xCD,0x2D,0xAD,0x6D,0xED,0x1D,0x9D,0x5D,0xDD,0x3D,0xBD,0x7D,0xFD,
0x03,0x83,0x43,0xC3,0x23,0xA3,0x63,0xE3,0x13,0x93,0x53,0xD3,0x33,0xB3,0x73,0xF3,
0x0B,0x8B,0x4B,0xCB,0x2B,0xAB,0x6B,0xEB,0x1B,0x9B,0x5B,0xDB,0x3B,0xBB,0x7B,0xFB,
0x07,0x87,0x47,0xC7,0x27,0xA7,0x67,0xE7,0x17,0x97,0x57,0xD7,0x37,0xB7,0x77,0xF7,
0x0F,0x8F,0x4F,0xCF,0x2F,0xAF,0x6F,0xEF,0x1F,0x9F,0x5F,0xDF,0x3F,0xBF,0x7F,0xFF};
const unsigned short masks[17] =
{0,0,0,0,0,0,0,0,0,0X0100,0X0300,0X0700,0X0F00,0X1F00,0X3F00,0X7F00,0XFF00};
unsigned long codeword; // value to be reversed, occupying the low 1-24 bits
unsigned char maxLength; // bit length of longest possible codeword (<= 24)
unsigned char sc; // shift count in bits and index into masks array
if (maxLength <= 8)
{
codeword = table[codeword << (8 - maxLength)];
}
else
{
sc = maxLength - 8;
if (maxLength <= 16)
{
codeword = (table[codeword & 0X00FF] << sc)
| table[codeword >> sc];
}
else if (maxLength & 1) // if maxLength is 17, 19, 21, or 23
{
codeword = (table[codeword & 0X00FF] << sc)
| table[codeword >> sc] |
(table[(codeword & masks[sc]) >> (sc - 8)] << 8);
}
else // if maxlength is 18, 20, 22, or 24
{
codeword = (table[codeword & 0X00FF] << sc)
| table[codeword >> sc]
| (table[(codeword & masks[sc]) >> (sc >> 1)] << (sc >> 1));
}
}
怎么样:
long temp = 0;
int counter = 0;
int number_of_bits = sizeof(value) * 8; // get the number of bits that represent value (assuming that it is aligned to a byte boundary)
while(value > 0) // loop until value is empty
{
temp <<= 1; // shift whatever was in temp left to create room for the next bit
temp |= (value & 0x01); // get the lsb from value and set as lsb in temp
value >>= 1; // shift value right by one to look at next lsb
counter++;
}
value = temp;
if (counter < number_of_bits)
{
value <<= counter-number_of_bits;
}
(我假设您知道有多少位值并存储在 number_of_bits 中)
显然 temp 需要是可以想象的最长的数据类型,当您将 temp 复制回 value 时, temp 中的所有无关位都应该神奇地消失(我认为!)。
或者,“c”方式是:
while(value)
你的选择
我们可以将所有可能的 1 字节序列反转的结果存储在一个数组(256 个不同的条目)中,然后使用对该表的查找和一些或逻辑的组合来获得整数的反转。
这是对 TK 解决方案的变化和修正,可能比 sundar 的解决方案更清晰。它从 t 中获取单个位并将它们推入 return_val:
typedef unsigned long TYPE;
#define TYPE_BITS sizeof(TYPE)*8
TYPE reverser(TYPE t)
{
unsigned int i;
TYPE return_val = 0
for(i = 0; i < TYPE_BITS; i++)
{/*foreach bit in TYPE*/
/* shift the value of return_val to the left and add the rightmost bit from t */
return_val = (return_val << 1) + (t & 1);
/* shift off the rightmost bit of t */
t = t >> 1;
}
return(return_val);
}
适用于任何类型、任何大小的对象的通用方法是反转对象的字节数,并反转每个字节中的位顺序。在这种情况下,位级算法与具体的位数(一个字节)相关,而“变量”逻辑(关于大小)则提升到整个字节的级别。
这是我对 freespace 解决方案的概括(以防有一天我们得到 128 位机器)。当使用 gcc -O3 编译时,它会产生无跳转代码,并且显然对理智机器上 foo_t 的定义不敏感。不幸的是,它确实取决于 Shift 是 2 的幂!
#include <limits.h>
#include <stdio.h>
typedef unsigned long foo_t;
foo_t reverse(foo_t x)
{
int shift = sizeof (x) * CHAR_BIT / 2;
foo_t mask = (1 << shift) - 1;
int i;
for (i = 0; shift; i++) {
x = ((x & mask) << shift) | ((x & ~mask) >> shift);
shift >>= 1;
mask ^= (mask << shift);
}
return x;
}
int main() {
printf("reverse = 0x%08lx\n", reverse(0x12345678L));
}
如果位反转对时间要求严格,并且主要与 FFT 结合使用,最好是存储整个位反转数组。无论如何,该数组的大小将小于必须在 FFT Cooley-Tukey 算法中预先计算的单位根。计算数组的一个简单方法是:
int BitReverse[Size]; // Size is power of 2
void Init()
{
BitReverse[0] = 0;
for(int i = 0; i < Size/2; i++)
{
BitReverse[2*i] = BitReverse[i]/2;
BitReverse[2*i+1] = (BitReverse[i] + Size)/2;
}
} // end it's all