excel二进制移位运算_位运算-秦斌的博客-51CTO博客

1.位运算介绍

程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了，就是直接对整数在内存中的二进制位进行操作。

2.位运算符号

Java中的运算符号：

& ： 按位与

|：按位或

^：按位异或

~：按位取反

<

>>：右移，左侧补符号位

>>>：右移，左侧补0

3.应用

3.1 Excel表格问题

在Excel中，用A表示第1列，B表示第2列......Z表示第26列，AA表示第27列，AB表示第28列......以此类推。请写出一个函数，输入用字母表示的列号编码，输出它是第几列：

解析：

A=1，B=2，C=3，......，Z=26

AA=(26^0 * 1) + (26^1 * 1) = 27;   注：^表示次方这里

AB=(26^0 * 2) + (26^1 * 1)= 28;

3.2 交换两个数字

在不使用额外空间的情况下交换两个数字：

解析：

一般解法：

位运算解法：

3.3 比较练习

对于两个32位整数a和b，请设计一个算法返回a和b中较大的。但是不能用任何比较判断。若两数相同，返回任意一个。public:

int Flip(int c)

{

return c^1;

}

int GetSign(int c)//非负为1，负为0.

{

return Flip((c>>31)&1);

}

int getMax(int a, int b)

{

int c=a-b;

int as=GetSign(a);//a的符号，as==1表示a为非负，as==0表示a为负

int bs=GetSign(b);//b的符号，bs==1表示b为非负，bs==0表示b为负

int cs=GetSign(c);//a-b的符号

int difab=as^bs;//表示a和b是否符号不相同，不相同为1，相同为0

int sam=Flip(difab);//表示a和b是否符号相同，相同为1，不相同为0

if(sam)

return cs?a:b;

else

return (as-bs)?a:b;

}

};

3.4 寻找奇数出现次数

有一个整型数组A，其中只有一个数出现了奇数次，其他的数都出现了偶数次，请打印这个数。要求时间复杂度为O(N),额外空间复杂度为O(1).

解析：

给定一个eo和一个已知数组，然后用eo与数组每个元素进行异或运算。

需要了解的是：任意调换整数异或的顺序不会改变最终的异或值：

所以最终的异或结构为：eo = D;

3.5 寻找整数出现的次数(两个数字)

给定一个整型数组arr，其中有两个数出现了奇数次，其他的数都出现了偶数次，找到这两个数。要求时间复杂度为O(N)，额外空间复杂度为O(1).

解析：

class OddAppearance {

public:

vector findOdds(vector arr, int n)

{

vector res;//假设最后得到的两个数是a，b

int check1=0;

for(int i=0;i

check1=check1^arr[i];

int k=0,temp=check1;

while(!(temp&1))//因为check1不为0，所以肯定存在第k为为1

{

k++;

temp>>=1;

}

int help=pow(2.0,k),check2=0;

for(int i=0;i

if(arr[i]&help)

check2=check2^arr[i];

check1=check1^check2;//check2为a和b其中一个数，则另外一个数是check1^check2

res.push_back(check1

res.push_back(check1>check2?check1:check2);

return res;

}

};

3.6 二进制中1的个数

实现一个函数，输入一个整数，输出该数二进制中表示1的个数。例如：输入9变成二进制位1001，输出2；

思路：先判断整数二进制表示中最右边一位是不是1，如果不是右移一位，再继续判断，直到整个整数变成0为止。一个整数与1做与运算的结果是1，表示整数最右边一位是1，否则是0。可以写出下面代码：int NumberOf1(int n){

int count = 0;

while(n){

if(n & 1)

count ++;

n = n >> 1;

}

return count;

}

问题：上面函数如果输入一个负数，比如0x80000000，运行的时候会出现死循环。因为把负数右移一位的时候，并不是简单把最高位移到第二位变成0x40000000,而是0xC0000000。这是因为移位前是个负数，仍然要保证移位后是个负数，因此移位后的最高位会设为1。如果一直做右移运算，最终这个数字就会变成0xFFFFFFFF而陷入死循环。

解决：不移动数字i，当i与1进行与运算并且判断后，左移1位再与i做与运算，这样就能判断i的次低位是不是1......这样反复左移，就可以判断：int NumberOf1(int n){

int count = 0;

unsigned int flag = 1;

while(flag){

if(n & flag)

count ++;

flag = flag <

}

return count;

}

上面算法需要循环32次，优化算法(有几个1循环几次)：把一个整数减去1，再和原来整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制中有多少1，就可以进行多少次这样的操作。int NumberOf1(int n){

int count = 0;

unsigned int flag = 1;

while(n){

++ count;

n = (n - 1) & n;

}

return count;

}

3.7 不用加减乘除做加法

int Add(int num1, int num2){

int sum, carry;

do{

sum = num1 ^ num2;

carry = (num1 & num2) <

num1 = sum;

num2 = carry;

}while(num2 != 0);

return num1;

}

3.8 hashmap中的hash算法

Java7：static int hash(int h) {

// This function ensures that hashCodes that differ only by

// constant multiples at each bit position have a bounded

// number of collisions (approximately 8 at default load factor).

//该函数确保每个位位置上只有常数倍数的哈希码具有有限的碰撞数(默认负载系数约为8)。

h ^= (h >>> 20) ^ (h >>> 12);

return h ^ (h >>> 7) ^ (h >>> 4);

}

Java8：/**

* Computes key.hashCode() and spreads (XORs) higher bits of hash

* to lower.  Because the table uses power-of-two masking, sets of

* hashes that vary only in bits above the current mask will

* always collide. (Among known examples are sets of Float keys

* holding consecutive whole numbers in small tables.)  So we

* apply a transform that spreads the impact of higher bits

* downward. There is a tradeoff between speed, utility, and

* quality of bit-spreading. Because many common sets of hashes

* are already reasonably distributed (so don't benefit from

* spreading), and because we use trees to handle large sets of

* collisions in bins, we just XOR some shifted bits in the

* cheapest possible way to reduce systematic lossage, as well as

* to incorporate impact of the highest bits that would otherwise

* never be used in index calculations because of table bounds.

*/

//计算键. hashcode()和扩展(XORs)，将散列的高位数降低。由于该表使用的是两种掩模，

//所以只在当前掩码上方的位上的散列集合总是会发生碰撞。(在已知的例子中，有一组浮点键，在小的表中保持连续的整数。)所以我们应用一个变换，

//将高位的影响传播到下。在速度、效用和比特传播质量之间存在权衡。因为许多常见的散列集已经合理分布(所以不要受益于传播),

//因为我们用树来处理大型的碰撞在垃圾箱,我们只是XOR一些改变以最便宜的方式来减少系统lossage,以及将最高位的影响,否则永远不会因为指数计算中使用的表。

static final int hash(Object key) {

int h;

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}