位运算

转载于：

http://220.181.111.15/%B7%E7%C0%D7%D1%B8%C1%D2/blog/item/bd38bb9e24790f116e068cd1.html

1) int型变量循环左移k次，即a=a < <k |a>>16-k (设sizeof(int)=16)
(2) int型变量a循环右移k次，即a=a>>k |a < <16-k (设sizeof(int)=16)
(3)整数的平均值
对于两个整数x,y，如果用 (x+y)/2 求平均值，会产生溢出，因为 x+y 可能会大于INT_MAX，但是我们知道它们的平均值是肯定不会溢出的，我们用如下算法：
int average(int x, int y) //返回X,Y 的平均值
{
return (x&y)+((x^y)>>1);
}

求两个数及三个数的最大值（推广到多个数）

求两个数的最大值，可以转化为求(a-b)的正负：

整型数据最高位（二进制）右移31位（Visual C/C++中整型是32位的，其它看系统分配情况）后，最低位就是右移前的最高位，再&1判断是1还是0；若是1则为a-b<0；0则a-b>0

int a,b,c;

max=(a-b)>>31&1?b:a; //a>b则max=a;a<b则max=b;此时的max表示a,b中的最大值

max=(max-c)>>31&1?c:max;//此时的max就表示a,b,c中的最大值
(4)判断一个整数是不是2的幂,对于一个数 x >= 0，判断他是不是2的幂
bool power2(int x)
{
    return ((x&(x-1))==0)&&(x!=0)；
}
(5)不用temp交换两个整数
void swap(int a , int b)
{
    a ^= b;
    b ^= a;
    a^= b;

//a^=b^=a^=b;
}

三种交换算法的总结

t=a;

a=b;

b=t

优点：不会溢出，可用于多种数据类型（指针，字符串等）缺点：多用一个变量

a=a+b;

b=a-b;

a=a-b;

优点：不增加变量。缺点：可能数值溢出。不能用于非数值交换

a^=b^=a^=b;

优点：速度快，不会数值溢出缺点：只能用于整型量交换
(6)计算绝对值
int abs( int x )
{
int y ;
y = x >> 31 ;
return (x^y)-y ;

//or: return (x+y)^y ;
}
(7)取模运算转化成位运算 (在不产生溢出的情况下)
        a % (2^n) 等价于 a & (2^n - 1)
(8)乘法运算转化成位运算 (在不产生溢出的情况下)
        a * (2^n) 等价于 a < < n
(9)除法运算转化成位运算 (在不产生溢出的情况下)
        a / (2^n) 等价于 a>> n
        例: 12/8 == 12>>3
(10) a % 2 等价于 a & 1
(11) if (x == a) x= b;
　   else x= a;
　　等价于 x= a ^ b ^ x;
(12) x 的相反数表示为 (~x+1)

(13)求从x位（高）到y位（低）间共有多少个1

int FindChessNum(int x, int y, ushort k)
        {
            int ret = 0;
            for (int i = y; i <= x; i++)
            {
                ret += ((k >> (i - 1)) & 1);
            }
            return ret;
        }
(14)
/*将32位数分解为4个8位数处理后再合成32位数返回*/
DWORD GetDW(DWORD dw)
{
DWORD dwRet=0;
if (dw!=0)
{
  BYTE b1=(dw>>24)&0xff,b2=(dw>>16)&0xff,b3=(dw>>8)&0xff,b4=dw&0xff;
  //分别处理 b1,b2,b3,b4
  dwRet=b1;
  dwRet=(dwRet<<8)+b2;
  dwRet=(dwRet<<8)+b3;
  dwRet=(dwRet<<8)+b4;

return dwRet;
}
else{
return 0;
}
}

/*
 * jlu2241.c
 *
 *  Created on: 2011-9-5
 *      Author: bjfuwangzhu
 */

#include<stdio.h>
int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif
    int i, j;
    while (scanf("%d %d", &i, &j) != EOF) {
        printf("%d\n", i ^ j);
    }
    return 0;
}

/*
 * jlu2243.c
 *
 *  Created on: 2011-9-5
 *      Author: bjfuwangzhu
 */
/*
 思路大概是先算出一的个数，接着用原来的数-1的个数就是进位的总数。
 想象下游N个1代表原来的数，多一个进位就少一个1，
 所以原来的数-现在1的个数就是进位数
 */
#include<stdio.h>
int solve(int n) {
    int res;
    res = 0;
    while (n) {
        res++;
        n = n & (n - 1);
    }
    return res;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif
    int n;
    while (scanf("%d", &n) != EOF,n) {
        printf("%d\n", n - solve(n));
    }
    return 0;
}