k*******9
发帖数: 7 | 1 是的，0100100010000111 -> 1110000100010010。
用的以前见过的这个算法：
Num = (Num & 0x55555555) << 1 | (Num >> 1) & 0x55555555;
Num = (Num & 0x33333333) << 2 | (Num >> 2) & 0x33333333;
Num = (Num & 0x0F0F0F0F) << 4 | (Num >> 4) & 0x0F0F0F0F;
Num = (Num & 0x00FF00FF) << 8 | (Num >> 8) & 0x00FF00FF;
Num = (Num & 0x0000FFFF) << 16 | (Num >> 16) & 0x0000FFFF;
|
|
m****n
发帖数: 589 | 2 int numberofones(unsigned int number)
{
if(number == 0)
return 0;
number = ((0xaaaaaaaa&number)>>1) + (0x55555555&number);
number = ((0xcccccccc&number)>>2) + (0x33333333&number);
number = ((0xf0f0f0f0&number)>>4) + (0x0f0f0f0f&number);
number = ((0xff00ff00&number)>>8) + (0x00ff00ff&number);
number = (number>>16) + (0x0000ffff&number);
return number;
} |
|
l******o
发帖数: 144 | 3 这个方法有意思。
int numberofones(unsigned int number)
{
if(number == 0)
return 0;
number = ((0xaaaaaaaa&number)>>1) + (0x55555555&number);
number = ((0xcccccccc&number)>>2) + (0x03333333&number);
number = ((0xf0f0f0f0&number)>>4) + (0x0f0f0f0f&number);
number = ((0xff00ff00&number)>>8) + (0x00ff00ff&number);
number = (number>>16) + (0x0000ffff&number);
return number;
} |
|
l******o
发帖数: 144 | 4
int numberofones(unsigned int number)
{
if(number == 0)
return 0;
number = ((0xaaaaaaaa&number)>>1) + (0x55555555&number);
number = ((0xcccccccc&number)>>2) + (0x03333333&number);
~~~~~~~
0x33333333吧
number = ((0xf0f0f0f0&number)>>4) + (0x0f0f0f0f&number);
number = ((0xff00ff00&number)>>8) + (0x00ff00ff&number);
number = (number>>16) + (0x00 |
|
r*********s
发帖数: 2157 | 5 x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
return((x >> 16) | (x << 16)); |
|
K******g
发帖数: 1870 | 6 不就是倒过来吗？
#define REVERSE((x)) (x)=(((x)&0xFFFF0000)>>16|((x)&0x0000FFFF)<<16) \
（x)=(((x)&0xFF00FF00)>>8|((x)&0x00FF00FF)<<8) \
（x)=(((x)&0xF0F0F0F0)>>4|((x)&0x0F0F0F0F)<<4) \
（x)=(((x)&0xCCCCCCCC)>>2|((x)&0x33333333)<<2) \
（x)=(((x)&0xAAAAAAAA)>>1|((x)&0x55555555)<<1) |
|
r**l
发帖数: 31 | 7
classic question bit reverse
lgn implementation, there are more efficient and fancy way of bit
operation, but this is most straightforward.
// assume 32 bits integer
unsigned int reverseBits(unsigned int x) {
x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
return((x >> 16) | (x << 16));
} |
|
g*******s
发帖数: 490 | 8 用& | 和 bit shift的方法有，只用& |的还真不知道
unsigned __int32 reversing_bits(unsigned __int32 input)
{
// complixity O(log [no.of.bits]) = O(1)
// On 32 bit machines it takes 5 steps (logical)
// Step 1
// Mask bit positions 0, 2, 4... shift LEFT this masked number by one
// Mask bit positions 1, 3, 5... shift RIGHT this masked number by one
input = (input & 0x55555555) << 1 | (input & 0xAAAAAAAA) >> 1;
// Step 2
// Mask bit positions 01, 45, 89... shift LEFT this masked number by ... 阅读全帖 |
|
o****o
发帖数: 1398 | 9 如果没有准备过，估计很多人面试遇到位运算的题目都会头疼，包括我自己，所以在此
总结一下位运算相关题目吧，从leetcode,careercup还有本版学到的，留个纪念：
1. Toggle 5th-8th bit of a 32bit Integer 这是我自己编的题，不过对于理解XOR操
作有帮助
Ans: a = a ^ 0x000000F0;
2. 交换第i与第j位
这个思路是直接：抠出第i位和第j位，交换之后再置位，可是实现比较麻烦啊，分情况
考虑比较好：
（1）如果第i位和第j位相同，不用换
（2）如果不同，用题1的方法，来个掩码，仅toggle第i位和第j位
Ans:
//Assume i,j start from 0
int exchange(int a, int i, int j) {
if( ((a>>i)&1) != ((a>>j)&1) ) {
a = a ^ ((1<
}
return a;
}
3. Turn off the rightmost 1-bit
Ans: x = x & (x-1)... 阅读全帖 |
|
l*******b
发帖数: 2586 | 10 int getBitsOne(int c)
{
c = ((c & 0xaaaaaaaa)>>1) + (c & 0x55555555);
c = ((c & 0xcccccccc)>>2) + (c & 0x33333333);
c = ((c & 0xf0f0f0f0)>>4) + (c & 0x0f0f0f0f);
c = ((c & 0xff00ff00)>>8) + (c & 0x00ff00ff);
c = ((c & 0xffff0000)>>16) + (c & 0x0000ffff);
return c;
} |
|
f*****r
发帖数: 229 | 11
treat
O(1)
it
C/C++.
Let us get the Linux version of bitcount:
/*
41 * hweightN: returns the hamming weight (i.e. the number
42 * of bits set) of a N-bit word
43 */
44
45 static inline unsigned int generic_hweight32(unsigned int w)
46 {
47 unsigned int res = (w & 0x55555555) + ((w >> 1) & 0x55555555);
48 res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
49 res = (res & 0x0F0F0F0F) + ((res >> 4) & 0x0F0F0F0F);
50 res = (res & 0x00FF00FF) + ((res >> 8) & 0x0 |
|
X****r
发帖数: 3557 | 12 这个……
直接方法：一位一位移位
取巧的方法：就地交换
实用的方法：查表，或部分查表和就地交换相结合。
就地交换方法如下，假设是32位无符号整数
x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);
x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2);
x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4);
x = ((x & 0xFF00FF00) << 8) | ((x & 0x00FF00FF) >> 8);
x = ((x & 0xFFFF0000) << 16) | ((x & 0x0000FFFF) >> 16); |
|
