时光博客

位运算

DIV7的位运算实现

题目如下

一个数除以7,不能用除法,乘法以及模运算,写出算法并实现

解题思路

既然不能用常规的函数,那么我们就像想别的办法,最容易想到的,当然还是位运算,关于位运算,leetcode上有一道题,属于经典的位运算题目,我博客之前也做过分析,猛击这里阅读「 Single Number II 

首先假设这个数为N,这个数可以表示为 N = 8 * A + B,为什么要用8,是因为8是最靠近7的,且可以通过二级制位移来产生的数字,例如:A >> 3 = A * 2 ^ 3 = A * 8

有了上面的结论后,那么就有了下面的递归

equation.png - 大小: 1.75 KB - 尺寸: 282 x 18 - 点击打开新窗口浏览全图

从上面的公式中很容易看出来递归,那么A、B究竟该怎么表示呢?回到公式 N = 8 * A + B,不难看出,

A = N / 8  且 B = N & 7

A = N / 8 很好理解,可以看做8是被除数,N是商

B = N & 7 这个又回到了,我们的位运算的与运算上,因为B < 8,所以要获得B 只需要获取 N 的二级制最小位开始的后三位即可,所以这里是 & 0111,直接返回后3位的值

上面的理解了,程序就很容易写出来了

代码如下

#include <stdio.h>
int div7(int n) {
    if(n < 8)
    {
        return (n + 1) >> 3; //此处+1是为了处理n为7的情况
    }
    else
    {
        return (n >> 3) + div7((n >> 3) + n & 7);
    }
}
int main(){
    int n = 14;
    int x;
    x = div7(n);
    printf("%d div 7 is : %d\n", n, x);
} 

编译之后运行 14 div 7 is : 2

这里留一道地考题,如何求 任意数正整数对7求余,同样不利用乘法、除法、取模

Single Number II

题目如下
Given an array of integers, every element appears three times except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

问题:给一个数组,里面只有一个数字一次,其它数字都出现3次,找出这个出现一次的数字,要求时间复杂度为O(n),空间复杂度为O(1)。

解题思路:

这里我们需要用到的知识为二进制、位计算。这里需要思考数字在计算机是怎么存储的。考虑全部用二进制表示,如果我们把第i个位置上所有数字的和对3取余,那么只会有两个结果 0 或 1 (根据题意,3个0或3个1相加余数都为0).

AC代码如下:

#include <stdio.h>
int singleNumber(int A[], int n) {
    int count[32] = {0};
    int result = 0;
    for (int i = 0; i < 32; i++) {
        for (int j = 0; j < n; j++) {
            //判断A[J]的第i位的奇偶,奇数才加,偶数为0不加
            if ((A[j] >> i) & 1) {
                count[i]++;
            }
        }
        // 计算第i位的和,然后计算其对应的10进制,再通过与运算求和(其实加法求和也可以)
        result |= ((count[i] % 3) << i);
    }
    return result;
}

我们可以用一组CASE来测试一下 {12, 1, 12, 3, 12, 1, 1,15, 3, 3}

最后依次统计各位上的和如下

qq20150515-1@2x.png - 大小: 12 KB - 尺寸: 168 x 423 - 点击打开新窗口浏览全图

依次为 4447,高位为0直接省略。最后求余之后为 为 1111,转换为2进制则为 8+4+2+1 = 15

算法中值得注意的是:

通过位运算 (A[j] >> i) & 1 来判断奇偶

因为此题又看了一下位运算,感觉CS的世界博大精深

©2008-2017 - 时光博客 Ucloud

京ICP备15052479号返回顶部