首页 > C/C++ > 二进制思考(四):位运算经典题目练习

二进制思考(四):位运算经典题目练习

2012年3月2日 发表评论 阅读评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

本文主要是基于《The C Programming Language》的位运算题目进行了一个整理,第一道题和第四道题都是该书中的题目,本节在这里给出一些可能的实现。

========目录=======

--二进制1的个数

--前导0的个数

--二进制逆序

--二进制循环移位

--高低位交换

==================

二进制1的个数

计算二进制1的个数,位运算可以有多种方法,本文实现了三种方法,前两种思想基本一样,细节不同,可对比看一下,欢迎讨论,代码如下

#include<stdio.h>

int bitcount_1(unsigned x); // 移位 n 次
int bitcount_2(unsigned x); // 移位 <= n 次
int bitcount_3(unsigned x); // 移位 count 次
void displaybits(int x); // 打印二进制

void main()
{
	int y = 521;
	displaybits(y);
	printf("%d\n",bitcount_3(y));
}
int bitcount_1(unsigned x)
{
	int count = 0;
	for(unsigned i = 1 << 31; i > 0; i >>= 1)//屏蔽码一般使用unsigned
	{
		if(x & i)
		{
			++count;
		}
	}
	return count;
}

int bitcount_2(unsigned x)
{
	int count = 0;
	for(; x > 0; x >>= 1)
	{
		if(x & 1)
		{
			++count;
		}
	}
	return count;
}

int bitcount_3(unsigned x)
{
	int count = 0;
	for(; x != 0; x &= (x-1))
	{
		++count;
	}
	return count;
}

void displaybits(int x)
{
	for(unsigned i = (1 << 31); i > 0; i >>= 1) //屏蔽码一般使用unsigned
	{
		printf("%c",x & i ? '1' : '0');
	}
	printf("\n");
}

=================================

前导0的个数

我的做法就是简单的使用屏蔽码自左向右做一个遍历计数,可参照上题打印二进制验证,这里不罗列测试程序。

int prezeroCount(int x)
{
	int count = 0;
	unsigned mask = 1 << 31; //屏蔽码一般使用unsigned
	while(0 == (x & mask))
	{
		++count;
		x <<= 1;
	}
	return count;
}

=================================

二进制逆序

我的想法是从右到左取位存在字符数组中,然后打印即可

#include<stdio.h>

#define INTBIT 32

void bitreverse(char *s, int x);

void main()
{
	int x = 1314520; //逆序为00011011011100000010100000000000
	char s[INTBIT+1] = {0};
	bitreverse(s,x);
	printf("%s\n",s);

}

void bitreverse(char *s, int x)
{
	int i = 0;
	for(; i < INTBIT; x >>= 1)
	{
		s[i++] = x & 1 ? '1' : '0';
	}
	s[i] = '\0';
}

=================================

二进制循环移位

编写一个函数shift(x,n),该函数返回将x循环右移(即从最右端移出的位将从最左端移入)n(二进制)位后所得到的值。

该题的解决思路其实就类似于《编程之美》中“数组循环移位”的思想,这里不再罗列分析。

根据位运算的不同变换,我提供了两种实现,其中第二种实现比较直观简单,欢迎讨论。

#include<stdio.h>

#define INTSEPR 32

void displaybits(int x);
void shift_1(int &x, int n);
void shift_2(int &x, int n);

void main()
{
	int x = 52, y = 52;
	displaybits(x);

	shift_1(x,13);
	displaybits(x);

	shift_2(y,13);
	displaybits(y);
}

void displaybits(int x)
{
	for(unsigned i = (1 << 31); i > 0; i >>= 1)
	{
		printf("%c",x & i ? '1' : '0');
	}
	printf("\n");
}

void shift_1(int &x, int n)
{
	n %= INTSEPR;
	unsigned i = (x & ~(~0<<n)) << (INTSEPR-n);
	unsigned j = x >> n;
	x = i | j;
}

void shift_2(int &x, int n)
{
	n &= 0x1f; // 对32取余的另一种方式
	x = (x << (INTSEPR-n)) | (x >> n);
}

=================================

高低位交换

高低位交换便是循环移位的简单版本,用上题的方法一句话便可实现。


x = (x << 16) | (x >> 16);

(全文完)

推荐阅读:

本文前三道题目在matrix67的博客中都有其他解法,感兴趣可以读一下,链接如下:

http://www.matrix67.com/blog/archives/264