[LintCode] A + B Problem（位運(yùn)算）

xiaolinbang 發(fā)布于2019-08-14 15:14 / 420人閱讀

摘要：位運(yùn)算筆記加法異或運(yùn)算求和與運(yùn)算進(jìn)位。減法將負(fù)數(shù)化為正，兩步完成取反做加法乘法的最后一位是，則結(jié)果每次循環(huán)后始終判斷最后一位，進(jìn)位累加小學(xué)生算式做乘法除法不贅述，

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

**位運(yùn)算筆記
Bit Manipulation Notes:**

加法：

^異或運(yùn)算：求和；

&與運(yùn)算：進(jìn)位。

減法：

將負(fù)數(shù)化為正：~i, +1，兩步完成取反

做加法

乘法：

a * b: if (b & 1) ans += a //b的最后一位是1，則結(jié)果+a

每次循環(huán)后a << 1, b >> 1; //b始終判斷最后一位，a進(jìn)位累加（小學(xué)生算式做乘法）

除法：（不贅述，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);
    }
}

GPU云服務(wù)器云服務(wù)器 bit位運(yùn)算按位運(yùn)算位運(yùn)算位運(yùn)算詳解

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65469.html

相關(guān)文章

[LintCode/LeetCode] Single Number I & II [位運(yùn)算]

摘要：整個(gè)過程相當(dāng)于，直接在和里去掉既是又是的。所以最后返回的，一定是只出現(xiàn)過一次的，而出現(xiàn)兩次的都在里，出現(xiàn)三次的都被消去了。 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 評(píng)論0 收藏0
[LintCode] Count 1 in Binary [典型位運(yùn)算題目]

摘要：這道題，給我解決了兩個(gè)疑問，還剩一個(gè)。首先是要用無符號(hào)右移運(yùn)算符，其次是可以用一個(gè)不斷左移的二進(jìn)制作為參照。 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 評(píng)論0 收藏0
[LintCode] Divide Two Integers

摘要：首先，分析溢出條件，設(shè)置符號(hào)位，然后取絕對(duì)值運(yùn)算。原理如下，被除數(shù)，除數(shù)，設(shè)等于。如，，，所以商里必定有一個(gè)的次方存入，然后。然后被除數(shù)減去，繼續(xù)。此時(shí)，，循環(huán)結(jié)束。再舉一個(gè)例子看得懂的版本綜合一下 Problem Divide two integers without using multiplication, division and mod operator. If it is ...

NervosNetwork 2019-08-14 15:16 評(píng)論0 收藏0
[LintCode] Binary Representation

摘要：細(xì)節(jié)上還要考慮正負(fù)號(hào)和整數(shù)位的越界情況。然后在循環(huán)內(nèi)判斷，如果有重復(fù)出現(xiàn)的，或者中小數(shù)部分的長度超過，就說明該小數(shù)無法完全轉(zhuǎn)換。如果之前的正負(fù)號(hào)為，就在左邊加上負(fù)號(hào)。 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 評(píng)論0 收藏0
[LintCode] Flip Bits

摘要：的二進(jìn)制補(bǔ)碼就是個(gè)，因此這道題一定要考慮正負(fù)號(hào)的問題。然后去檢查的二進(jìn)制包含多少個(gè)，方法是對(duì)的每一位除以取余。如果為，就說明那一位為，即和在那一位不同，需要進(jìn)行轉(zhuǎn)換。每次取余之后，減小為二分之一，刪除已經(jīng)檢查過的高位。 Problem Determine the number of bits required to flip if you want to convert integer...

joyvw 2019-08-14 15:21 評(píng)論0 收藏0