常見位運算總結(jié)

1.基礎(chǔ)位運算

<<：表示左移

>>：表示右移

~：表示每一位取反

&：表示“且”，有0則0

|：表示“或”，有1則1

^：異或操作，相同為0，相異為1（無進位相加）

2.給一個數(shù)，確定它的二進制表示中的第x位是0還是1

計算(n>>x)&1

• 為1：第x位是1
• 為0：第x位是0

3.將一個數(shù)n的二進制表示的第x位修改成1

n=n|(1<<x)

4.將一個數(shù)n的二進制表示的第x位修改成0

n=n&(~(1<<x))

5.提取一個數(shù)n二進制表示中最右側(cè)的1

只提取出最右邊的1，說明左邊的可以不要（為0）

n&-n

6.去掉一個數(shù)n二進制表示中最右側(cè)的1

只去掉最右邊的1，說明左邊的不變

n&(n-1)

一、判斷字符是否唯一

題目鏈接：https://leetcode.cn/problems/is-unique-lcci/description/

題目：

實現(xiàn)一個算法，確定一個字符串 s 的所有字符是否全都不同。

示例 1：輸入：s = "leetcode"輸出：false

示例 2：輸入：s = "abc"輸出：true

限制：

• 0<=len(s)<=100
• s [i] 僅包含小寫字母
• 如果你不使用額外的數(shù)據(jù)結(jié)構(gòu)，會很加分。

思路：

這道題使用了位圖的思想。

我們需要一個數(shù)bitmap=0，讓它的每一個二進制位的數(shù)字來表示字母是否出現(xiàn)過。

首先：如果字符串的長度大于26，那必定有重復(fù)的字符出現(xiàn)。

當我們遍歷字符串時，拿出對應(yīng)的字符找到在位圖中對應(yīng)的位置，判斷該位置是否為1，如果為1，說明這個字符串是重復(fù)了的，返回false；如果為0，則將位圖中對應(yīng)的位置修改為1，直到遍歷完整個字符串。

代碼及結(jié)果：

class Solution {
    public boolean isUnique(String astr) {
        if(astr.length()>26) return false;
        int bitmap=0;//建立一個位圖，有32位
        //對應(yīng)字符位置的元素為1，則說明有該字符
        for(int i=0;i<astr.length();i++){
            int x=astr.charAt(i)-'a';
            //判斷位圖中是否有該字符
            if(((bitmap>>x)&1)==1) return false;
            //將該字符加入到位圖中
            bitmap|=1<<x;
        }
        return true;
    }
}

二、

題目鏈接：https://leetcode.cn/problems/missing-number/

題目：

給定一個包含 [0,n] 中 n 個數(shù)的數(shù)組 nums，找出 [0,n] 這個范圍內(nèi)沒有出現(xiàn)在數(shù)組中的那個數(shù)。

示例 1：

輸入：nums=[3,0,1]

輸出：2

解釋：n=3，因為有 3 個數(shù)字，所以所有的數(shù)字都在范圍 [0,3] 內(nèi)。2 是丟失的數(shù)字，因為它沒有出現(xiàn)在 nums中。

示例 2：

輸入：nums=[0,1]

輸出：2

解釋：n=2，因為有 2 個數(shù)字，所以所有的數(shù)字都在范圍 [0,2] 內(nèi)。2 是丟失的數(shù)字，因為它沒有出現(xiàn)在 nums中。

示例 3：

輸入：nums=[9,6,4,2,3,5,7,0,1]

輸出：8

解釋：n=9，因為有 9 個數(shù)字，所以所有的數(shù)字都在范圍 [0,9] 內(nèi)。8 是丟失的數(shù)字，因為它沒有出現(xiàn)在 nums中。

思路：

使用位運算中的異或運算（無進位相加）。

把數(shù)組中所有元素異或起來，再將0～n的所有數(shù)也異或起來，就能兩兩消除相同的數(shù)。

代碼及結(jié)果：

class Solution {
    public int missingNumber(int[] nums) {
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum=sum^(nums[i]^i);
        }
        sum=sum^nums.length;
        return sum;
    }
}

三、兩整數(shù)之和

題目鏈接：https://leetcode.cn/problems/sum-of-two-integers/

題目：

給你兩個整數(shù) a 和 b，不使用運算符 + 和 -，計算并返回兩整數(shù)之和。

示例 1：輸入：a = 1，b = 2輸出：3

示例 2：輸入：a = 2，b = 3輸出：5

思路：

本題要求不能使用運算符，所以使用位運算解決。

首先，使用無進位相加a^b，

至于進位操作：在異或結(jié)果的基礎(chǔ)上找出哪些是需要進位的(a&b)<<1，

將a^b作為新的a，將(a&b)<<1作為新的b，繼續(xù)重復(fù)以上操作，直到不需要進位，即b為0。

代碼及結(jié)果：

class Solution {
    public int getSum(int a, int b) {
        while(b!=0){
            int x=a^b;//先計算出a和b無進位相加結(jié)果
            b=(a&b)<<1;
            a=x;
        }
        return a;
    }
}

四、只出現(xiàn)一次的數(shù)字Ⅱ

題目鏈接：https://leetcode.cn/problems/single-number-ii/description/

題目：

給你一個整數(shù)數(shù)組 nums，除某個元素僅出現(xiàn)一次外，其余每個元素都恰出現(xiàn)三次。請你找出并返回那個只出現(xiàn)了一次的元素。

你必須設(shè)計并實現(xiàn)線性時間復(fù)雜度的算法且使用常數(shù)級空間來解決此問題。

示例 1：輸入：nums = [2,2,3,2]輸出：3

示例 2：輸入：nums = [0,1,0,1,0,1,99]輸出：99

思路：

除目標數(shù)外，每一個數(shù)的二進制的每一位要么為0要么為1，則所有數(shù)的對應(yīng)的二進制位數(shù)相加，應(yīng)該為3n個0或者3n個1（n表示整數(shù)），將其與目標數(shù)的對應(yīng)二進制位相加后%3：

當結(jié)果為0，則目標數(shù)該位數(shù)為0；

當結(jié)果為1，則目標數(shù)該位數(shù)為1；

代碼及結(jié)果：

class Solution {
    public int singleNumber(int[] nums) {
        int ret=0;//要查找的那個數(shù)字
        for(int i=0;i<32;i++){//依次遍歷位圖的每一位
            int sum=0;//用于存放所有數(shù)字第i位之和
            for(int x:nums){
                if(((x>>i)&1)==1){
                    sum++;
                }
            }
            ret=ret^((sum%3)<<i);
        }
        return ret;
    }
}

五、消失的兩個數(shù)字

題目鏈接：https://leetcode.cn/problems/missing-two-lcci/

題目：

給定一個數(shù)組，包含從 1 到 N 所有的整數(shù)，但其中缺了兩個數(shù)字。你能在 O (N) 時間內(nèi)只用 O (1) 的空間找到它們嗎？

以任意順序返回這兩個數(shù)字均可。

示例 1：輸入：[1]輸出：[2,3]

示例 2：輸入：[2,3]輸出：[1,4]

思路：

這道題依舊使用位運算的思想，我們將數(shù)組和1～N之間的數(shù)都異或起來，這時得到的數(shù)為x1和x2的異或。

首先x1和x2一定不相等，所以x1和x2異或的結(jié)果的二進制位中一定有“1”，假設(shè)1在第x位，則x1在x位的數(shù)是與x2的不同的。

假設(shè)x1在x位為0，x2在x位為1，我們再將所有的數(shù)分為兩類：

一類在x位為0，它們異或之后結(jié)果就為x1；

一類在x位為1，它們異或之后結(jié)果就為x2.

代碼及結(jié)果：

class Solution {
    public int[] missingTwo(int[] nums) {
        int ans[]=new int[2];
        //轉(zhuǎn)化為：只出現(xiàn)一次的數(shù)字3
        int ret=0;//存放x1^x2
        int n=nums.length;
        for(int x:nums){
            ret^=x;
        }
        for(int i=1;i<=n+2;i++){
            ret^=i;
        }
        //此時ret=x1^x2;

        //在nums中和1到N的所有數(shù)中找到x1和x2
        //1 先找到ret中最右邊的1所在位置
        ret=ret&(-ret);
        int x1=0,x2=0;
        //說明x1和x2在這個位置的值不一樣,假如x1此處為0，x2此處為1
        for(int x:nums){
            if((x&ret)==0){//說明x在這個位置的數(shù)為0，與x1分為一類
                x1^=x;
            }else{
                x2^=x;
            }
        }
        for(int i=1;i<=n+2;i++){
            if((i&ret)==0){//說明x在這個位置的數(shù)為0，與x1分為一類
                x1^=i;
            }else{
                x2^=i;
            }
        }
        ans[0]=x1;
        ans[1]=x2;
        return ans;
    }
}

總結(jié) 

到此這篇關(guān)于Java優(yōu)選算法之位運算的文章就介紹到這了,更多相關(guān)Java位運算內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論