[LintCode] A + B Problem（位运算）

xiaolinbang 发布于2019-08-14 15:14 / 253人阅读

摘要：位运算笔记加法异或运算求和与运算进位。减法将负数化为正，两步完成取反做加法乘法的最后一位是，则结果每次循环后始终判断最后一位，进位累加小学生算式做乘法除法不赘述，

Problem

Write a function that add two numbers A and B. You should not use + or any arithmetic operators.

Example

Given a=1 and b=2 return 3

Challenge

Of course you can just return a + b to get accepted. But Can you challenge not do it like that?

Note

**位运算笔记
Bit Manipulation Notes:**

加法：

^异或运算：求和；

&与运算：进位。

减法：

将负数化为正：~i, +1，两步完成取反

做加法

乘法：

a * b: if (b & 1) ans += a //b的最后一位是1，则结果+a

每次循环后a << 1, b >> 1; //b始终判断最后一位，a进位累加（小学生算式做乘法）

除法：（不赘述，O(log n)）

http://blog.csdn.net/ojshilu/article/details/11179911

Solution

class Solution {
    public int aplusb(int a, int b) {
        // write your code here, try to do it without arithmetic operators.
        if (b == 0) return a;
        int sum = a^b;
        int carry = (a&b) << 1;
        return aplusb(sum, carry);
    }
}

私有云云服务器 bit位运算按位运算位运算位运算详解

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65469.html

[LintCode/LeetCode] Single Number I & II [位运算]

摘要：整个过程相当于，直接在和里去掉既是又是的。所以最后返回的，一定是只出现过一次的，而出现两次的都在里，出现三次的都被消去了。 Single Number I Problem Given 2*n + 1 numbers, every numbers occurs twice except one, find it. Example Given [1,2,2,1,3,4,3], return...

Drinkey 2019-08-14 15:33 评论0 收藏0
[LintCode] Count 1 in Binary [典型位运算题目]

摘要：这道题，给我解决了两个疑问，还剩一个。首先是要用无符号右移运算符，其次是可以用一个不断左移的二进制作为参照。 Problem Count how many 1 in binary representation of a 32-bit integer. Example Given 32, return 1 Given 5, return 2 Given 1023, return 9 Ch...

ZHAO_ 2019-08-14 15:16 评论0 收藏0
[LintCode] Divide Two Integers

摘要：首先，分析溢出条件，设置符号位，然后取绝对值运算。原理如下，被除数，除数，设等于。如，，，所以商里必定有一个的次方存入，然后。然后被除数减去，继续。此时，，循环结束。再举一个例子看得懂的版本综合一下 Problem Divide two integers without using multiplication, division and mod operator. If it is ...

NervosNetwork 2019-08-14 15:16 评论0 收藏0
[LintCode] Binary Representation

摘要：细节上还要考虑正负号和整数位的越界情况。然后在循环内判断，如果有重复出现的，或者中小数部分的长度超过，就说明该小数无法完全转换。如果之前的正负号为，就在左边加上负号。 Problem Given a (decimal - e.g. 3.72) number that is passed in as a string, return the binary representation t...

you_De 2019-08-14 15:21 评论0 收藏0
[LintCode] Flip Bits

摘要：的二进制补码就是个，因此这道题一定要考虑正负号的问题。然后去检查的二进制包含多少个，方法是对的每一位除以取余。如果为，就说明那一位为，即和在那一位不同，需要进行转换。每次取余之后，减小为二分之一，删除已经检查过的高位。 Problem Determine the number of bits required to flip if you want to convert integer...

joyvw 2019-08-14 15:21 评论0 收藏0