荔园在线
荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: mmkiller (傢有小魔§好好学习,天天翘课), 信区: Program
标 题: 一些有关C++语言中的bit操作zz
发信站: 荔园晨风BBS站 (2005年12月03日20:38:34 星期六), 站内信件
[code]
Author:Jeff 2005-11-30
关键字:C/C++ bit 位操作
以下大多从网上和书中来,有些则加入了个人的见解~~
1) 函数实现交换两个int型变量的值,要求不定义任何中间变量。
C / C++ 版:
void Swap(int *a, int *b)
{
*a^=*b;
*b^=*a;
*a^=*b;
}
C++ 版:
void Swap(int &a, int &b)
{
a^=b;
b^=a;
a^=b;
}
分析一下:
(a ^ b = s) (b ^ s = a)
0 ^ 1 = 1 1 ^ 1 = 0
1 ^ 0 = 1 0 ^ 1 = 1
1 ^ 1 = 0 1 ^ 0 = 1
0 ^ 0 = 0 0 ^ 0 = 0
归结一下:1. 两个数相异或,相同的位清0,不同的位置1。 (所以才有了 XOR eax, eax
;eax清零)
2. s = (a ^ b); (b ^ s) == a ? Yes. 异或加密解密的基础.
2) 摘自《高效程序的奥秘》一书。英文书名<Hacker’s Delight>,译为《黑客的窃喜》
获得后缀0bit的个数。(从低位开始的连续的0bit,间接地求最低位的1bit的位置)
int ntz(unsigned x) { // Number of trailing zeros.
int n;
if (x == 0) return(32);
n = 1;
if ((x & 0x0000FFFF) == 0) {n = n +16; x = x >>16;}
if ((x & 0x000000FF) == 0) {n = n + 8; x = x >> 8;}
if ((x & 0x0000000F) == 0) {n = n + 4; x = x >> 4;}
if ((x & 0x00000003) == 0) {n = n + 2; x = x >> 2;}
return n - (x & 1);
}
3) 除了最低位的bit1,其余位全清0. <Hacker’s Delight>一书。
n = n & (-n) < - - - - > n = n & (~n + 1)
分析一下:
假设n(2) = X…X10…0。其中每个X代表bit值并不都是相同,0的个数≥0,ˉX表示该位取
反。
X & ˉX = 0, 1 & 0 = 0
则~n(2) = ˉX…ˉX01…1。
~n + 1 = ˉX…ˉX10…0。
n & (~n + 1) = 0…010…0
4) 清最低位的bit1,其他不变。
n = n & (n – 1);
则 n – 1 = X…X01…1
n & (n - 1) = X…X00…0
5) 获得bit1的个数。(统计)
我们常用的方法:
int Get1BitCount(unsigned int x)
{
int n = 0;
while (x > 0) {
if (x & 0x1) n++;
x >>= 1;
}
return n;
}
另一种更好的办法:
int Get1BitCount(unsigned int x)
{
int n = 0;
while (x > 0) {
n++;
x = x & (x - 1);
}
return n;
}
6) 求unsigned int型数一共有多少bit?(网上看到有人问)
int nCount = Get1BitCount((unsigned int)~0);
求别的数据类型的位数,要重载Get1BitCount(或者直接用temlate来实现)。
不过觉得像上面这样求法,太浪费了,不是吗?
int GetTotalBit(void)
{
unsigned int x = ~0;
int n = 0;
while (x > 0) {
n += 8;
x >>= 8;
}
return n;
}
7) 清除低位到高位的n个bit1。
while (--n > 0) {
x = x & (x - 1);
}
[/code]
--
*[0;3*┌─╮˙ ╭ ╭╮╭╭─╮╭┬╮*BigcatNAT 透明代理 功能*
*├─┤│╭─╮╭─ ╭─╮-┼-│││├─┤ │ *自 动 过 滤 收 费 连 接*
*└─╯│╰─│╰─╯╰─╰ ╰ ╰╰╯╰ ╯ ╰ *简 化 软 件 代 理 设 置*
*╰─╯ *0 5 年 3 月 最 新 2 . 0 测 试 版 发 布*
* *详 细 功 能 说 明 及 软 件 下 载 , 请 连 接 至 下 面 的 地 址 *
*http://www.flashszu.com/BigcatNAT* *Powered by BiGcAt.NET *
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 61.141.170.120]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店