//Compute modulus division by 1 << s without a division operator
const unsigned int n; // numerator
const unsigned int s;
const unsigned int d = 1U << s; // So d will be one of: 1, 2, 4, 8, 16, 32, ...
unsigned int m; // m will be n % d
m = n & (d - 1);
//Compute modulus division by (1 << s) - 1 without a division operator , 微软面试题 :用位运算实现n%7, 即n%(2^3 - 1) , 答案如下
unsigned int n; // numerator , dp n%7 =( (n/8)*(8-7) + n%8) %7 = (n>>3 + n&7)%7 , 不断转化，直到括号内小于等于7为止
(1)
m = n>>3 + n&7;
while(m>7)
{
m = m>>3 + m&7;
}
if(m ==7) return 0;
else return m;
(2)
const unsigned int s =3; // s > 0
const unsigned int d = (1 << s) - 1; // so d is either 1, 3, 7, 15, 31, ...).
unsigned int m; // n % d goes here.
for (; n > d; n = m)
{
for (m = 0; n; n >>= s)
{
m += n & d;
}
}
// Now m is a value from 0 to d, but since with modulus division
// we want m to be 0 when it is d.
m = m == d ? 0 : m;
int add(int x,int y)
{
int m,n;
m = x& y; //需要进位的位
n = x^y; //进位后的状态
while(m)
{
n = m<<1 ^ n;
m = m<<1 & n;
}
return n;
}
unsigned int div(unsigned int a , unsigned int b)
{
int i;
unsigned int m = 0;
for(i = 1 ; i<= 32 ;i=add(i,1))
{
m = m<<1 | a>> 31;
a = a<<1;
if(m>=b)
{
m = add(m,b);
a = add(a,1); //其实可以为a|=1;或a^=1;
}
}
return a;
}
//计算v二进制表示中1的个数
unsigned int v; // count bits set in this (32-bit value)
static const int S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers
static const int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};
v = (v>>S[0])+ ((v >>S[0]) & B[0]);
v = (v&B[1])+ ((v>> S[1]) & B[1]);
v = (v&B[2])+ ((v>> S[1]) & B[2]);
v = (v&B[3])+ ((v>> S[1]) & B[3]);
v = (v&B[4])+ ((v>> S[1]) & B[4]);
//将v比特反转注意最后一位是怎么移到第一位的
// swap odd and even bits
v = ((v >>S[0]) & B[0]) | ((v & B[0]) <
// swap consecutive pairs
v = ((v >>S[1]) & B[1]) | ((v & B[1]) <// swap nibbles
v = ((v >>S[2]) & B[2]) | ((v & B[2]) <// swap bytes
v = ((v >>S[3]) & B[3]) | ((v & B[3]) <// swap 2-byte long pairs
v = ((v >>S[4]) & B[4]) | ((v & B[4]) <
//Find the log base 2 of an N-bit integer in O(lg(N)) operations 二分查找
unsigned int v; // 32-bit value to find the log2 of
register unsigned int r; // result of log2(v) will go here
register unsigned int shift;
r = (v > 0xFFFF) << 4; v >>= r;
shift = (v > 0xFF ) << 3; v >>= shift; r |= shift;
shift = (v > 0xF ) << 2; v >>= shift; r |= shift;
shift = (v > 0x3 ) << 1; v >>= shift; r |= shift;
r |= (v >> 1);
//Find integer log base 10 of an integer the obvious way
static unsigned int const PowersOf10[] =
{1, 10, 100, 1000, 10000, 100000,
1000000, 10000000, 100000000, 1000000000};
r = (v >= 1000000000) ? 9 : (v >= 100000000) ? 8 : (v >= 10000000) ? 7 :
(v >= 1000000) ? 6 : (v >= 100000) ? 5 : (v >= 10000) ? 4 :
(v >= 1000) ? 3 : (v >= 100) ? 2 : (v >= 10) ? 1 : 0;
//Find integer log base 2 of a 32-bit IEEE float
const float v; // find int(log2(v)), where v > 0.0 && finite(v) && isnormal(v)
int c; // 32-bit int c gets the result;
c = *(const int *) &v; // OR, for portability: memcpy(&c, &v, sizeof c);
c = (c >> 23) - 127;
//Count the consecutive zero bits (trailing) on the right linearly
//Count the consecutive zero bits (trailing) on the right by binary search
unsigned int v; // 32-bit word input to count zero bits on right
unsigned int c; // c will be the number of zero bits on the right,
// so if v is 1101000 (base 2), then c will be 3
// NOTE: if 0 == v, then c = 31.
if (v & 0x1)
{
// special case for odd v (assumed to happen half of the time)
c = 0;
}
else
{
c = 1;
if ((v & 0xffff) == 0)
{
v >>= 16;
c += 16;
}
if ((v & 0xff) == 0)
{
v >>= 8;
c += 8;
}
if ((v & 0xf) == 0)
{
v >>= 4;
c += 4;
}
if ((v & 0x3) == 0)
{
v >>= 2;
c += 2;
}
c -= v & 0x1;
}
阅读(906) | 评论(0) | 转发(0) |
