常見(jiàn)位運(yùn)算總結(jié)

1.基礎(chǔ)位運(yùn)算

<<：表示左移

>>：表示右移

~：表示每一位取反

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

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

^：異或操作，相同為0，相異為1（無(wú)進(jìn)位相加）

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

計(jì)算(n>>x)&1

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

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

n=n|(1<<x)

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

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

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

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

n&-n

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

只去掉最右邊的1，說(shuō)明左邊的不變

n&(n-1)

一、判斷字符是否唯一

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

題目：

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

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

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

限制：

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

思路：

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

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

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

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

代碼及結(jié)果：

class Solution {
    public boolean isUnique(String astr) {
        if(astr.length()>26) return false;
        int bitmap=0;//建立一個(gè)位圖，有32位
        //對(duì)應(yīng)字符位置的元素為1，則說(shuō)明有該字符
        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/

題目：

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

示例 1：

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

輸出：2

解釋?zhuān)簄=3，因?yàn)橛?3 個(gè)數(shù)字，所以所有的數(shù)字都在范圍 [0,3] 內(nèi)。2 是丟失的數(shù)字，因?yàn)樗鼪](méi)有出現(xiàn)在 nums中。

示例 2：

輸入：nums=[0,1]

輸出：2

解釋?zhuān)簄=2，因?yàn)橛?2 個(gè)數(shù)字，所以所有的數(shù)字都在范圍 [0,2] 內(nèi)。2 是丟失的數(shù)字，因?yàn)樗鼪](méi)有出現(xiàn)在 nums中。

示例 3：

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

輸出：8

解釋?zhuān)簄=9，因?yàn)橛?9 個(gè)數(shù)字，所以所有的數(shù)字都在范圍 [0,9] 內(nèi)。8 是丟失的數(shù)字，因?yàn)樗鼪](méi)有出現(xiàn)在 nums中。

思路：

使用位運(yùn)算中的異或運(yùn)算（無(wú)進(jìn)位相加）。

把數(shù)組中所有元素異或起來(lái)，再將0～n的所有數(shù)也異或起來(lái)，就能兩兩消除相同的數(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/

題目：

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

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

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

思路：

本題要求不能使用運(yùn)算符，所以使用位運(yùn)算解決。

首先，使用無(wú)進(jìn)位相加a^b，

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

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

代碼及結(jié)果：

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

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

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

題目：

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

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

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

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

思路：

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

當(dāng)結(jié)果為0，則目標(biāo)數(shù)該位數(shù)為0；

當(dāng)結(jié)果為1，則目標(biāo)數(shù)該位數(shù)為1；

代碼及結(jié)果：

class Solution {
    public int singleNumber(int[] nums) {
        int ret=0;//要查找的那個(gè)數(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;
    }
}

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

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

題目：

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

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

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

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

思路：

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

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

假設(shè)x1在x位為0，x2在x位為1，我們?cè)賹⑺械臄?shù)分為兩類(lèi)：

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

一類(lèi)在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;
        }
        //此時(shí)ret=x1^x2;

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

總結(jié) 

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

最新評(píng)論