Error

C++博客 首页 新随笔 联系 聚合 管理
  217 Posts :: 61 Stories :: 32 Comments :: 0 Trackbacks
int comput(int tmpn)
  int tmpc=0;
   while(tmpn>0)
   {
     tmpc++;
     tmpn=tmpn&(tmpn-1)
    }
  return tmpc;
}




x=x&(x-1)
==============
以前没有见过这样的表达式,分析一下发现发明这个表达式的人是个高手。
表达式的意思就是把x的二进制表示从最低位直到遇到第一个1的比特置0。
例如:
e1:
x     = 01001000
x-1   = 01000111
x&(x-1)=01000000
e2:
x     = 01001001
x-1   = 01001000
x&(x-1)=01001000

位运算里有学问呀,
例如众所周知的交换算法:
void swap(int i1, int i2)
{
    i1 ^= i2;
    i2 ^= i1;
    i1 ^= i2;
}
还有,我今天看了Minix操作系统作者写的《操作系统 设计与实现》(写的比William Stalling的《操作系统 内核与设计原理》有条理而且清晰紧凑得多,后者内容芜杂)中的页面替换算法之一矩阵法,就是用位运算实现的:
假设内存分为n页,那么高速缓存一个n x n的比特矩阵,开始时全置0,如下(假设n=4):
  0 1 2 3
0 0 0 0 0
1 0 0 0 0
2 0 0 0 0
3 0 0 0 0
每次内存访问时,如果访问的是i页,那么先把矩阵的第i行置1,然后把矩阵的第i列置0,这样i行的二进制的值越小就表示i页最长时间最近没有被访问。例如假设访问的次序为0-2-3-1,那么该矩阵的变化过程为:
  0 1 2 3
0 0 1 1 1    0 1 0 1    0 1 1 0    0 0 1 0
1 0 0 0 0    0 0 0 0    0 0 0 0    1 0 1 1
2 0 0 0 0    1 1 0 1    1 1 0 0    1 0 0 0
3 0 0 0 0    0 0 0 0    1 1 1 0    1 0 1 0
第三个例子是Windows GDI的二元和三元光栅操作的编码。比较复杂,就不讲了。

x=x&(x-1); 可以用来求出x是否为2幂次方数;当&的结果为0时,x原值是2幂次方数,否则就不是2幂次方数;
如x=4时   4: 0000 0100
        & 3:0000 0011
得出结果为0 ,是2幂次方数;
x=5时,  0000 0101
         0000 0100
得出结果为1,即非2幂次方数;

posted on 2014-02-26 16:55 Enic 阅读(597) 评论(0)  编辑 收藏 引用 所属分类: 面试小算法

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理