Home Tags Posts tagged with "位运算"

位运算

使用异或运算实现两数交换

~无关风月~ 2016-01-01 23:51:24 13830 收藏 20
文章标签: 算法
通常我们实现两数交换不得不引入一个临时变量temp作为媒介,而使用异或运算也能实现同样的功能,甚至无需使用临时变量。

这是一个通常的做法:

int main(){
int a=1,b=2,temp;
temp=a;
a=b;
b=temp;
printf(“%d,%d\n”,a,b);
return 0;
}

关于异或(Exclusive OR)
Wikipedia解释

在数位逻辑中,逻辑算符互斥或闸(exclusive or)是对两个运算元的一种逻辑分析类型,符号为XOR或EOR或⊕。与一般的或闸OR不同,当两两数值相同为真..而有一数值不同时为否..

两个运算元(命题):A与B的异或一般写成A异或B,或者写成A \quad \mathrm{XOR} \quad B、A \oplus B、A \neq B等等。在C语言中,写作A^B。

两个相同数的异或结果为0
异或真值表
A B A^B
0 0 0
0 1 1
1 0 1
1 1 0
异或的小例子

假设a为二进制数01,b为二进制数10,a^b的结果为11并将其存储在变量c中,经过反复的测试,于是发现以下的规律:

11^01=10
11^10=01
c^a=b;
c^b=a;
可以很惊奇的发现,将两数异或的结果与其中一数再进行异或,可以得到另一个数。
原理很简单,两数异或的结果保存了两个数上每一个二进制位不同或相同的信息,如果相应的二进制位不同,就标志为1,如果相同,则标志为0。
由于任意一个二进制位与1异或有这样一个特性:

0^1=1
1^1=0
即与1异或后,都将自己转换成相反的位

这样,我们就使用异或运算交换了两数

12(001100)

^ 34(100010)

——————-

101110

101110 ^ 001100=100010

101100 ^ 100010=001100

int main(){
int a=12,b=34,temp;
printf(“Original result: a=%d,b=%d\n”,a,b);
temp=a^b;
a=temp^a;
b=temp^b;
printf(“Transformed result: a=%d,b=%d\n”,a,b);
return 0;
}
result //
Original result: a=12,b=34
Transformed result: a=34,b=12

但是使用这种方法似乎与使用临时变量没有什么区别?

其实不然,通过简单分析可以发现临时变量的值在整个过程中并没有发生变化,因此也可以无需设置临时变量。

a=a^b^a;
b=a^b^b;
于是可以使用第三种方法,将a设置为临时变量

a=a^b;
b=b^a;
a=b^a;
还可以写得更简洁一点:
a^=b^=a^=b;

还可以通过加减实现两数互换:

a=a+b

b=a-b;

a=a-b;

前提是a+b的值不能溢出。

测试程序如下:

int main()
{
int a = 4, b = 5;
printf(“a=%d b=%d\n”, a, b);
a = a ^ b;
b = a ^ b;
a = a ^ b;
printf(“a=%d b=%d\n”, a, b);
}

运行结果:
[root@test cs]# ./a.out
a=4 b=5
a=5 b=4
[ 注意:当a和b相等时,该方法不适用]

其他方法:

public void change1(int a, int b){
System.out.println(“change1交换之前\ta:”+a+”\tb:”+b);
a = a + b – (b = a);
System.out.println(“change1交换之后\ta:”+a+”\tb:”+b);
}
public void change2(int a, int b){//C/C++ 不适用
System.out.println(“change2交换之前\ta:”+a+”\tb:”+b);
b = a + (a = b)*0;
System.out.println(“change2交换之后\ta:”+a+”\tb:”+b);
}
public void change4(int a, int b){
System.out.println(“change4交换之前\ta:”+a+”\tb:”+b);
a = a * b;
b = a / b;
a = a / b;
System.out.println(“change4交换之后\ta:”+a+”\tb:”+b);
}

0 78
/**
 * 这是一份文档注释;第二章作业(编程题)
 *work 1.0;
 * 以如下结尾:位运算;
1.实现奇数相加;
class Scratch{
    public static void main(String[]args) {
        System.out.println("实现100以内奇数相加");
        int sum = 0, i = 0;
        for (i = 0; i < 100; i++) {
            if (i % 2 != 0) {
                sum += i;
            }
        }
        System.out.println("和为" + sum);
    }
}
2.冒泡排序;
class Scratch {
    public static void main(String[] args) {
        int i = 0, j = 0;
        int arr[] = new int[]{25, 24, 12, 76, 101, 96, 28};
        for (i = 0; i < arr.length - 1; i++) {
            for (j = 0; j < arr.length - 1 - i; j++) {
                int temp;
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }//冒泡排序;
        for (i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
        System.out.println("The Length of the array is "+arr.length);
    }
}*/
注意:与C不同,java不可i&1判断奇数偶数;
java中的if()条件为true和false,只能为布尔类型;
C语言中的if()条件为非0和0,甚至可以为字符;

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
请你返回该链表所表示数字的 十进制值 。
示例 1:
输入:head = [1,0,1]
输出:5
解释:二进制数 (101) 转化为十进制数 (5)
解题思路:把head链表的数挨个取出,再使用二进制转换
方法一:
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
int getDecimalValue(struct ListNode* head){
    struct ListNode* a=head;
    int i=0,arr[50]={0},sum=0,j=0;
    while(a!=NULL){
        arr[i]=a->val;
        a=a->next;
        i++;
    }
    i=i-1;
    //转换成二进制;
    for(;i>=0;i–){
        sum=sum+(arr[i]*pow(2,j));
        j++;
    }//已完成;
    return sum;
}
优化版:
#define null 0
int getDecimalValue(struct ListNode* head){
struct ListNode *a=head;
int num=0;
while(a!=null){
num=num*2+a->val;
a=a->next;
}
return num;
}
最优解:位运算(移位,或)
思路:位运算
每取 1 位数字,将当前所有数位 左移 1 位
通过位运算 或 将取出数字存入最低位
int getDecimalValue(struct ListNode* head){
int res = 0;
for ( ; head; head = head->next)
res = (res << 1) | head->val;
return res;
}