如何用位運算實現整數的加減法

Worktile 發布于2019-08-20 11:22 / 2147人閱讀

摘要：假設，，先把，轉化為二進制，那么，，二進制的加法是逢進，如果兩個數的同一位的基數分別是和，那么這個位上的基數為如果都是，則基數為如果都是，則基數為。

今天刷Leecode刷到第371題：

Sum of Two Integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example:
Given a = 1 and b = 2, return 3.

Credits:
Special thanks to @fujiaozhu for adding this problem and creating all test cases.

Subscribe to see which companies asked this question

題目要求我們在不使用加減操作符的情況下得到兩個整數的和。由于減法和乘除法都是基于加法操作的，所以此題不能考慮‘+’、‘-’、‘*’、’/‘這四個操作符，我們使用位運算來得到兩個數的和。
假設a = 15， b = 9，先把a，b轉化為二進制，那么a = 1111，b = 1001，二進制的加法是逢2進1，如果兩個數的同一位的基數分別是0和1，那么這個位上的基數為1；如果都是1，則基數為0；如果都是0，則基數為0。這種方式類似于位運算中的異或，只有兩個數字不等的時候結果才為1，那我們是不是可以直接用a ^ b來得到a + b的值呢？當然不行，當同一位上兩個基數都為1時，此時該位上的基數變為0，但是應該在它的左邊一位加1，異或運算并沒有給它加1，所以我們還得把逢2進1的那個1加進去，01 + 01 = 10，所以兩個數有一個位上的基數都是1的時候相加就類似于與運算，但是要把結果左移一位，因為它是在比它高一位的地方進1，相當于是乘以2了。于是兩個二進制的加法就轉化成了兩部分，一部分是兩個數同一位上的基數同為1的值，這部分的值用（a & b）<<1 可以得到，另一部分的值可以用異或得到，即 a ^ b，所以 a + b = a ^ b + (a & b）<<1.
在上一例中，

(a & b)<<1 = (1111 & 1001)<<1 = 10010;
 a ^ b = 1111 ^ 1001 = 110;
 a + b = 10010 + 110 = 11000 = 24

完整的代碼如下：

var getSum = function(a, b) {
    //注意"+"的優先級大于"<<"，所以要先把（a & b)<<1括起來
    var s = (a ^ b) + ((a & b)<<1)
    return s 
};

異或還有一個特點就是，一個整數與0異或的結果就等于它自己，它和自己異或等于0，這個結論能幫我們解決第136題。

[Single Number][2]

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Subscribe to see which companies asked this question

要找出一個數組里唯一的那個數，這時候我們很自然就想到了異或的特點，即：

a ^ 0 = a
a ^ a = 0
a ^ b ^ a = a ^ a ^ b = 0 ^ b = b

所以這道題我們利用for循環將數組里的所有元素異或，最終得到的就是那個只出現了一次的數，代碼如下：

var singleNumber = function(nums) {
    var result = 0
   for(var i = 0; i < nums.length; i++) {
       result = result ^ nums[i] 
   } 
   return result
};

可見有時候位運算的作用也很大呢！

GPU云服務器云服務器如何用webrtc實現聊天如何用c語言實現組合如何用js實現模態框如何用php實現客服

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/80542.html

【手把手帶你刷LeetCode】——15.劍指offer之不用加減乘除做加法（位運算）

摘要：前言今天是力扣打卡第天天天做遞歸做煩了，換換腦子，嘿嘿。原題不用加減乘除做加法題目描述寫一個函數，求兩個整數之和，要求在函數體內不得使用四則運算符號。補碼的優勢加法減法可以統一處理只有加法器。【前言】今天是力扣打卡第15天！天天做遞歸做煩了，換換腦子，嘿嘿。原題：不用加減...

QLQ 2021-11-15 11:38 評論0 收藏0
「干貨」細說 Javascript 中的浮點數精度丟失問題（內附好課推薦）

摘要：前言最近，朋友問了我這樣一個問題在中的運算結果，為什么是這樣的雖然我告訴他說，這是由于浮點數精度問題導致的。由于可以用階碼移動小數點，因此稱為浮點數。它的實現遵循標準，使用位精度來表示浮點數。 showImg(https://segmentfault.com/img/remote/1460000018981071); 前言最近，朋友 L 問了我這樣一個問題：在 chrome 中的運算...

senntyou 2019-08-23 17:06 評論0 收藏0
Javascript 基本概念（操作符）

摘要：對于有符號的整數，第一位是符號位正數，負數，后位表示數值。正數二進制表示，沒有用到的位補，如用二進制表示為，第一位是符號位，后位均用補位，是有效位。按位非求反碼，本質是求操作數的負值減一。 showImg(https://segmentfault.com/img/remote/1460000014827639); 操作符一元操作符只能操作一個值的操作符叫一元操作符 ++ and ...

Paul_King 2019-08-22 17:09 評論0 收藏0
js-數據運算

摘要：跳過第二個運算子的機制，被稱為短路有些程序員喜歡用它取代結構等價于運算符可以多個連用返回第一個布爾值為的表達式的值。一、運算符概述 1、定義 JavaScript中運算符主要用于連接簡單表達式，組成一個復雜的表達式 2、運算符類別算數運算符賦值表達式比較表達式布爾運算符位運算符二、算數運算符 1、加法運算符（Addition）：x + y 加法運算符是在運行時決定，到...

sf190404 2019-08-26 12:24 評論0 收藏0