整数位反转，无视整数大小和字节顺序 [英] Bit reversal of an integer, ignoring integer size and endianness
问题描述
给出的整数类型定义：
的typedef无符号整数类型;
或
的typedef unsigned long类型类型;
我有以下的code扭转一个整数位：
TYPE max_bit =（TYPE）-1;无效reverse_int_setup（）
{
TYPE位=（TYPE）max_bit; 而（比特下;＆下; = 1）
max_bit =位;
}TYPE reverse_int（TYPE ARG）
{
TYPE bit_setter = 1，bit_tester = max_bit，结果为0; 对于（结果= 0; bit_tester; bit_tester＆GT;＆GT; = 1，bit_setter＆LT;＆LT; = 1）
如果（ARG＆安培; bit_tester）
结果| = bit_setter;
返回结果;
}
一个只需要先运行reverse_int_setup（），存储与最高位整数打开，那么任何调用reverse_int（ ARG 的）返回 ARG 的其反转位（被用作一键的二进制树，从增加的计数器取，但是这或多或少无关）。
是否有一个平台无关的方式在编译时），以对MAX_INT正确的值，来电后reverse_int_setup（;否则，有没有你考虑一个算法的更好/更精简的比我有reverse_int（）？
感谢。
＃包括LT＆;＆stdio.h中GT;
＃包括LT＆;＆limits.h中GT;＃定义TYPE_BITS的sizeof（TYPE）* CHAR_BIT无符号的typedef长类型;反向型（N型）
{
TYPE NREV = 0，I，第1位，第2位;
诠释计数; 对于（I = 0; I＆下; TYPE_BITS; I + = 2）
{
/ *在每次迭代中，我们换一个位上的右半边
与另一对左一半数量的* / 数= TYPE_BITS - 我 - 1; / *这是用来寻找多少位置
向左（右），我们得动
在本次迭代中的位* / 位1 = N＆安培; （1 <<;≤（I / 2））; / *提取右半边位* /
第1位＆LT;＆LT; =计数; / *它移其所属的地方* / 第2位= N＆安培; 1 LT;≤（（I / 2）+计）; / *找到左半边位* /
第2位＆GT;＆GT; =计数; / *将在第1位的原始位置*位/ NREV | =第1位; / *现在位添加到逆转的结果* /
NREV | =第2位;
}
返回NREV;
}诠释的main（）
{
TYPE N = 6; 的printf（％吕氏春秋，反向（N））;
返回0;
}
我已经使用了从传统知识观念的比特数，但使它较为通过不假定一个字节便携式这次包含8位，而是使用CHAR_BIT宏。在code现在更有效率（与内循环删除）。我希望code也略少神秘的这个时候。 ：）
的需要使用计数是位置的数量，使我们必须转移一个位在每一次迭代变化 - 我们有31位置（假定32位的数字），第二个最右边的位29来移动最右边的位位置等。因此必须算在每次迭代，因为我的增加减少。
希望在了解了code产品介绍的是位被证明是有用的...
Given an integer typedef:
typedef unsigned int TYPE;
or
typedef unsigned long TYPE;
I have the following code to reverse the bits of an integer:
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;
}
One just needs first to run reverse_int_setup(), which stores an integer with the highest bit turned on, then any call to reverse_int(arg) returns arg with its bits reversed (to be used as a key to a binary tree, taken from an increasing counter, but that's more or less irrelevant).
Is there a platform-agnostic way to have in compile-time the correct value for max_int after the call to reverse_int_setup(); Otherwise, is there an algorithm you consider better/leaner than the one I have for reverse_int()?
Thanks.
#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;
}
This time I've used the 'number of bits' idea from TK, but made it somewhat more portable by not assuming a byte contains 8 bits and instead using the CHAR_BIT macro. The code is more efficient now (with the inner for loop removed). I hope the code is also slightly less cryptic this time. :)
The need for using count is that the number of positions by which we have to shift a bit varies in each iteration - we have to move the rightmost bit by 31 positions (assuming 32 bit number), the second rightmost bit by 29 positions and so on. Hence count must decrease with each iteration as i increases.
Hope that bit of info proves helpful in understanding the code...
这篇关于整数位反转，无视整数大小和字节顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
