# Bit Twiddling Hacks

####1.不用sizeof判断int占几个字节

``````#include <stdio.h>
int main(int argc, char* argv[])
{
unsigned int a = ~0;
int i = 1;
while ( (a = a >> 1) )
{
i++;
}
printf("%d byte %d bits\n", i / 8, i);
return 0;
}
``````

####2. 交换整型的奇数位和偶数位

``````#include <stdio.h>

int SwapOddEvenBit(int x)
{
return ( ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
}
int main(int argc, char* argv[])
{
int a = 171;
printf("%d\n", SwapOddEvenBit(a));
return 0;
}
``````

####3. 将整数的某几位改成给成的位序列

EXAMPLE Input: N = 10000000000 M = 10101, i = 2, j = 6 Output: N = 10001010100

SOLUTION：This code operates by clearing all bits in N between positon i and j , and then ORing to put M in there.

``````unsigned int updateBits(unsigned int  n, unsigned int m, int i, int j)
{
int max = ~0;

unsigned int left = max - ((1 << j) -1);
unsigned int right = ((1 << i) -1);

unsigned int mask = left | right;

return (n & mask) | (m << i);
}
``````

#### 4. 编写一个C表达式，使它生成一个字，由x的最低有效字节和y中剩下的字节组成。

``````return (x & 0xFF) | (y & ~0xFF)
``````

####5. 编写一个C表达式，在下列描述的条件下产生1,而在其他情况下得到0。假设x是int型。

• x的任何位都等于1

``````  return !(~x)
``````
• x的任何位都等于0

``````  return !x
``````
• x的最高有效字节中的位都等于1

``````  n = ((sizeof(int) - 1 ) << 3)
!( ~(x >> n))
``````
• x的最低有效字节中的位都等于0

``````  !(x&0xff)
``````

####6. 编写一个函数`int_shifts_are_logical()`，在对int类型的数使用算术右移的机器上运行时，这个函数返回1,其他情况下，返回0

``````int int_shifts_are_logical()
{
x = ~0;
return (x >> 1) = x;
}
``````

####7. 判断是否给定的数，奇数位不都全是0

``````	int any_even_one(unsigned x)
{
return x & (0xAAAAAAAA)
}
``````

####8. 对于给定的无符号整数，判断它的二进制表示中，1的个数为奇数

``````/* Return 1 when x contains an even number of 1s; 0 otherwise.
Assume w = 32*/

int even_ones(unsigned x)
{
x ^= x >> 16;
x ^= x >> 8;
x ^= x >> 4;
x ^= x >> 2;
x ^= x >> 1;
return ( ! x&1 );
}
``````

####9. 旋转整数的bit，对于给定的无符号整数x和n，将x的二进制表示向右旋转n位

``````/* Do rotating right shift. Assume 0 <= n < w
* Example when x = 0x12345678 and w = 32:
* n = 4 -> 0x81234567, n = 20 -> 0x45678123
*/
unsigned rotate_right(unsigned x, int n)
{
int w = sizeof(x) << 3;
int max = ~0;
left = max - ((1 << n) - 1);
right = ( 1 << n ) - 1;
return ((x & left) >> n) | (x & right << (w - n));
}
``````

####10.Detect if two integers have opposite signs

``````int x, y;               // input values to compare signs

bool f = ((x ^ y) < 0); // true iff x and y have opposite signs
Manfred Weis suggested I add this entry on November 26, 2009.
``````

####11. Determining if an integer is a power of 2

``````unsigned int v; // we want to see if v is a power of 2
bool f;         // the result goes here

f = (v & (v - 1)) == 0;
Note that 0 is incorrectly considered a power of 2 here. To remedy this, use:
f = v && !(v & (v - 1));
``````

####12. Counting bits set, Brian Kernighan’s way

``````unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
v &= v - 1; // clear the least significant bit set
}
``````

[1]: CSAPP DATA LAB

[2]: Hacker’s Delight

/
Published under (CC) BY-NC-SA in categories 程序语言  tagged with C语言  位操作