预备知识
对于位运算,大家都很熟悉,基本的位操作有与、或、非、异或等等。在面试中经常会出现位运算相关的题,所以我就做了简单的整理,参考了很多写的很好的博客及书籍。
现在简单说一下,移位运算。
左移运算:x << y。将x左移y位,将x最左边的y位丢弃,在右边补y个0。
右移运算:x >> y。将x右移y位,这需要区分x是有符号数还是无符号数。在x是无符号数时,只需将x的最右边的y位丢弃,在左边补上y个0。在x是有符号数时,又分为x是正数还是负数。正数时,同无符号数的处理相同;负数时,将将x的最右边的y位丢弃,在左边补上y个1。
位运算技巧
计算一个数的二进制中1的个数
通过与初始值为1的标志位进行与运算,判断最低位是否为1;然后将标志位左移,判断次低位是否为1;一直这样计算,直到将每一位都判断完毕。
/*
计算一个数的二进制中1的个数
*/
int countOf1(int num)
{
int count = 0;
unsigned int flag = 1;
while(flag)
{
if(num & flag)
{
count++;
}
flag = flag << 1;
}
return count;
}
还有一种方法,一个整数减一,可以得到该整数的最右边的1变为0,这个1右边的0变为1。对这个整数和整数减一进行与运算,将该整数的最右边的1变为0,其余位保持不变。直到该整数变为0,进行的与运算的次数即为整数中1的个数。
/*
计算一个数的二进制中1的个数
*/
int countOf1_2(int num)
{
int count = 0;
while(num)
{
num = num & (num - 1);
count++;
}
return count;
}
判断一个数是否是2的n次方
一个数是2的n次方,则这个数的最高位是1,其余位为0。根据上一题的第二种解法可以很容易得到解决方案。将这个整数与整数减一进行与运算,如果得到的结果为零,可证明该数为2的n次方。
/*
判断一个数是否为2的n次方(一个数为2的n次方,则最高位为1,其余位为0)
*/
bool is2Power(int num)
{
bool flag = true;
num = num & (num - 1); //计算num和num - 1的与的结果
if(num) //如果结果为0,则不是2的n次方
{
flag = false;
}
return flag;
}
整数n经过多少步可以变为整数m
n和m的异或结果可以得知两数不同位的个数,再调用计算一个数中1的个数的方法,即可得到结果。
/*
求解n变化为m,需要进行的操作步数
*/
int countChange(int n,int m)
{
n = n ^ m; //求n和m的异或,再计算结果中1的个数
return countOf1_2(n);
}
获得最大的int值
/*
获取最大的int
得到结果:2147483647
*/
int getMaxInt()
{
return (1 << 31) - 1;
}
/*
使用g++编译,出现warning: left shift count is negative
*/
int getMaxInt_2()
{
return (1 << -1) - 1;
}
int getMaxInt_3()
{
return ~(1 << 31);
}
/*
在不了解int的长度情况下使用
*/
int getMaxInt_4()
{
return ((unsigned int) -1) >> 1;
}
获得最小的int值
与获得最大的int方法类似。
/*
求最小int
得到结果:-2147483648
*/
int getMinInt()
{
return 1 << 31;
}
/*
同样在g++下编译,出现warning: left shift count is negative
*/
int getMinInt_2()
{
return 1 << -1;
}
获得最大的long
/*
求最大long
得到结果:9223372036854775807
*/
long getMaxLong()
{
return ((unsigned long) -1) >> 1;
}
判断一个数的奇偶性
判断奇偶性,实质是判断最后一位是否是1.
/*
判断一个数的奇偶性.返回1,为奇数;返回0,为偶数
*/
bool isOdd(int num)
{
return num & 1 == 1;
}
交换两个数(不借助第三变量)
不用第三个变量交换两个数的方法也有几种,例如a = a + b; b = a - b; a = a - b。下面这种方法可以实现的基础是一个数m与另一个数n异或,再与n异或,得到的结果是m.
/*
不适用临时变量,交换两个数
a = a ^ b
b = b ^ a
a = a ^ b
*/
void mySwap(int* a,int* b)
{
(*a) ^= (*b) ^= (*a) ^= (*b);
}
求一个数的绝对值
下面的方法实现的基础是将n右移31位,可以获得n的符号。
/*
取绝对值
n右移31位,可以获得n的符号。若n为正数,得到0;若n为负数,得到 -1
*/
int myAbs(int n){
return (n ^ n >> 31) - (n >> 31);
}
求两个数的平均值
第一种方法较为普遍且简单,不多说了。第二种方法,需要知道的是,( m ^ n ) >> 1得到的结果是m和n其中一个数的有些位为1的值的一半,m & n得到的结果是m 和n都为1的那些位,两个结果相加得到m和n的平均数。
/*
求m和n的平均数
*/
int getAverage(int m,int n){
return (m + n) >> 1;
}
/*
求m和n的平均数
(m ^ n) >> 1 -> 获得m和n两个数中一个数的某些位为1的一半
m & n -> 获得m和n两个数中都为1的某些位
*/
int getAverage_2(int m,int n){
return ((m ^ n) >> 1) + (m & n);
}
求解倒数第m位相关问题
/*
获取n的倒数第m位的值(从1开始计数)
*/
int getMthByTail(int n,int m){
return (n >> (m - 1)) & 1;
}
/*
将n的倒数第m位设为1
*/
int setMthByTail21(int n,int m)
{
return n | (1 << (m - 1));
}
/*
将n的倒数第m位设为0
*/
int setMthByTail20(int n,int m)
{
return n & ~(1 << (m - 1));
}
分享到:
相关推荐
在C/C++与汇编语言混合编程的情况下,一般我们都会选择C/C++来实现所期待的大部分功能,对于少数和硬件关联度高(例如操作某些CPU寄存器)以及对运算的实时性要求高(例如高速、多点的FFT)的功能才使用汇编来实现,这就...
快速幂取模,一个运算技巧,用的着的话可以下载看下,自己做题常用它,
《C/C++程序设计》全面地讲述了C/C++语言...全书共分为12章,主要内容包括:c语言概述、基本程序设计、程序控制结构、数组、函数、指针、结构体与共用体、位运算、文件、C++基础知识、面向对象程序设计及应用程序实例等
目前现有的C和C++的教材书籍中对于位运算的讲解和阐述较为简略,大多都是出于知识体系完整性的考虑而涉及了一些位运算符及其简单的应用 ].这对一些学习程序设计的人来说远远不够,很多学生仅仅知道有位运算符的存在...
11. C语言中的位运算 46 12. 浮点数的存储格式: 50 13. 位域 58 14. C语言函数二维数组传递方法 64 15. C语言复杂表达式的执行步骤 66 16. C语言字符串函数大全 68 17. C语言宏定义技巧 89 18. C语言实现动态数组 ...
11. C语言中的位运算 46 12. 浮点数的存储格式: 50 13. 位域 58 14. C语言函数二维数组传递方法 64 15. C语言复杂表达式的执行步骤 66 16. C语言字符串函数大全 68 17. C语言宏定义技巧 89 18. C语言实现动态数组 ...
11. C语言中的位运算 46 12. 浮点数的存储格式: 50 13. 位域 58 14. C语言函数二维数组传递方法 64 15. C语言复杂表达式的执行步骤 66 16. C语言字符串函数大全 68 17. C语言宏定义技巧 89 18. C语言实现动态数组 ...
11. C语言中的位运算 46 12. 浮点数的存储格式: 50 13. 位域 58 14. C语言函数二维数组传递方法 64 15. C语言复杂表达式的执行步骤 66 16. C语言字符串函数大全 68 17. C语言宏定义技巧 89 18. C语言实现动态数组 ...
11. C语言中的位运算 46 12. 浮点数的存储格式: 50 13. 位域 58 14. C语言函数二维数组传递方法 64 15. C语言复杂表达式的执行步骤 66 16. C语言字符串函数大全 68 17. C语言宏定义技巧 89 18. C语言实现动态数组 ...
11. C语言中的位运算 46 12. 浮点数的存储格式: 50 13. 位域 58 14. C语言函数二维数组传递方法 64 15. C语言复杂表达式的执行步骤 66 16. C语言字符串函数大全 68 17. C语言宏定义技巧 89 18. C语言实现动态数组 ...
11. C语言中的位运算 46 12. 浮点数的存储格式: 50 13. 位域 58 14. C语言函数二维数组传递方法 64 15. C语言复杂表达式的执行步骤 66 16. C语言字符串函数大全 68 17. C语言宏定义技巧 89 18. C语言实现动态数组 ...
11. C语言中的位运算 46 12. 浮点数的存储格式: 50 13. 位域 58 14. C语言函数二维数组传递方法 64 15. C语言复杂表达式的执行步骤 66 16. C语言字符串函数大全 68 17. C语言宏定义技巧 89 18. C语言实现...
基本运算写法:在C/C++ 编程中值得学习的那些算法。能够解决除法运算效率低的问题。提高程序的运行速度。提高程序的执行效率。减少因算法带来的内存消耗和性能低下的问题。你值得拥有的那些小技巧。
此外,本书通过对C++思想和历史的讨论、对经典实例(如矩阵运算、文本处理、测试以及嵌入式系统程序设计)的展示,以及对C语言的简单描述,为你呈现了一幅程序设计的全景图。 ·C++初学者的权威指南。无论你是从事...
此外,本书通过对C++思想和历史的讨论、对经典实例(如矩阵运算、文本处理、测试以及嵌入式系统程序设计)的展示,以及对C语言的简单描述,为你呈现了一幅程序设计的全景图。 ·C++初学者的权威指南。无论你是从事...
此外,本书通过对C++思想和历史的讨论、对经典实例(如矩阵运算、文本处理、测试以及嵌入式系统程序设计)的展示,以及对C语言的简单描述,为你呈现了一幅程序设计的全景图。 ·C++初学者的权威指南。无论你是从事...
此外,本书通过对C++思想和历史的讨论、对经典实例(如矩阵运算、文本处理、测试以及嵌入式系统程序设计)的展示,以及对C语言的简单描述,为你呈现了一幅程序设计的全景图。 ·C++初学者的权威指南。无论你是从事...
此外,本书通过对C++思想和历史的讨论、对经典实例(如矩阵运算、文本处理、测试以及嵌入式系统程序设计)的展示,以及对C语言的简单描述,为你呈现了一幅程序设计的全景图。 ·C++初学者的权威指南。无论你是从事...
此外,本书通过对C++思想和历史的讨论、对经典实例(如矩阵运算、文本处理、测试以及嵌入式系统程序设计)的展示,以及对C语言的简单描述,为你呈现了一幅程序设计的全景图。 ·C++初学者的权威指南。无论你是从事...