按位與（Bitwise AND）和按位異或（Bitwise XOR）

按位與（&）

按位與是對兩個數的二進制表示的每一位進行邏輯與操作。

規則：兩個對應位都為1時，結果位才為1，否則為0。

示例：

5 & 35 的二進制：0101
3 的二進制：0011
-----------
按位與：0001 (即1)

按位異或（^）

按位異或是對兩個數的二進制表示的每一位進行邏輯異或操作。

規則：兩個對應位不同時，結果位為1，相同時為0。

示例：

5 ^ 35 的二進制：0101
3 的二進制：0011
-----------
按位異或：0110 (即6)

特性

按位與特性：

• x & 0 = 0
• x & x = x
• x & ~x = 0
• 可用于檢查奇偶性：x & 1（結果為1則是奇數，0則是偶數）

按位異或特性：

• x ^ 0 = x
• x ^ x = 0
• x ^ y = y ^ x（交換律）
• (x ^ y) ^ z = x ^ (y ^ z)（結合律）
• 可用于交換兩個變量的值（不使用臨時變量）：

  a ^= b;
  b ^= a;
  a ^= b;
  

應用場景

按位與常見用途：

1. 掩碼操作（提取特定位）
2. 判斷奇偶性
3. 權限系統中檢查權限

按位異或常見用途：

1. 交換兩個變量的值
2. 加密算法
3. 查找唯一出現一次的數字（其他數字都出現兩次）
4. 圖形學中的顏色混合

這兩種位操作在底層編程、算法優化和嵌入式系統中經常使用。

完整的按位運算

除了按位與（AND）和按位異或（XOR）外，還有以下幾種常見的按位運算：

1. 按位或（Bitwise OR） |

對兩個數的二進制表示的每一位進行邏輯或操作。

規則：兩個對應位中只要有一個為1，結果位就為1。

示例：

5 | 35 的二進制：0101
3 的二進制：0011
-----------
按位或：0111 (即7)

特性：

• x | 0 = x
• x | x = x
• x | ~x = ~0（全1）
• 常用于設置特定位為1

2. 按位非（Bitwise NOT） ~

對一個數的二進制表示的每一位進行取反操作（一元運算符）。

規則：0變1，1變0。

示例：

~55 的二進制：0101
-----------
按位非：1010 (在4位表示中為-6，具體取決于數據類型長度)

注意：結果取決于數值的位數和表示方式（補碼表示法）。

3. 左移（Left Shift） <<

將二進制數向左移動指定位數，右側補0。

效果：相當于乘以2的n次方（無溢出時）。

示例：

5 << 25 的二進制：0101
左移2位：010100 (即20)

4. 右移（Right Shift） >>

將二進制數向右移動指定位數，左側補符號位（算術右移）或補0（邏輯右移，取決于語言）。

效果：相當于除以2的n次方（向下取整）。

示例：

5 >> 15 的二進制：0101
右移1位：0010 (即2)

5. 無符號右移（Zero-fill Right Shift） >>>（某些語言如Java、JavaScript）

將二進制數向右移動指定位數，左側總是補0。

示例：

-5 >>> 1 (在32位系統中)-5 的二進制：11111111111111111111111111111011
無符號右移1位：01111111111111111111111111111101 (一個大正數)

復合賦值運算符

所有位運算符都有對應的復合賦值形式：

• &= (按位與賦值)
• |= (按位或賦值)
• ^= (按位異或賦值)
• <<= (左移賦值)
• >>= (右移賦值)
• >>>= (無符號右移賦值)

應用總結

運算符	名稱	用途示例
&	按位與	掩碼操作、權限檢查
l	按位或	設置特定位
^	按位異或	交換值、加密、找唯一數
~	按位非	取反操作
<<	左移	快速乘以2的冪
>>	右移	快速除以2的冪（算術右移）
>>>	無符號右移	處理無符號數的右移（邏輯右移）

這些位運算在底層編程、算法優化、嵌入式系統開發、圖形處理和加密算法中都有廣泛應用。

Java 實現：查找唯一出現一次的數字（其他數字都出現兩次）

方法思路

1. 異或運算特性：

   • 任何數和 0 異或等于它本身：x ^ 0 = x ， 0 在異或運算中相當于“無影響”
   • 任何數和自身異或等于 0：x ^ x = 0
   • 異或運算滿足交換律和結合律：a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b

2. 算法步驟：

   • 初始化 result = 0。
   • 遍歷數組，對每個元素執行 result ^= num。
   • 最終 result 就是唯一出現一次的數字。

代碼實現

public class SingleNumber {public static int singleNumber(int[] nums) {int result = 0; // 初始時 result=0，不影響第一次運算for (int num : nums) {result ^= num;}return result;}public static void main(String[] args) {int[] nums = {4, 1, 2, 1, 2};System.out.println("唯一出現一次的數字是: " + singleNumber(nums)); // 輸出: 4}
}

代碼解釋

1. 方法 singleNumber：

   • 初始化 result 為 0。
   • 使用增強 for 循環遍歷數組 nums，對每個元素 num 執行異或操作 result ^= num。
   • 最終返回 result，即唯一出現一次的數字。

2. 主方法 main：

   • 定義一個測試數組 nums，其中 4 是唯一出現一次的數字。
   • 調用 singleNumber 方法并打印結果。

復雜度分析

• 時間復雜度：O(n)，只需遍歷數組一次。
• 空間復雜度：O(1)，僅使用常數空間存儲 result。

示例運行

輸入：[4, 1, 2, 1, 2]
輸出：唯一出現一次的數字是: 4

進階問題

如果數組中有兩個數字只出現一次，其他數字都出現兩次，如何找出這兩個數字？
提示：

1. 先異或所有數字得到 xorSum。
2. 找到 xorSum 的任意一個為 1 的位（如最低位的 1）。
3. 根據該位將數組分成兩組，分別異或得到兩個唯一數字。

Java 實現示例：

public static int[] findTwoSingleNumbers(int[] nums) {int xorSum = 0;for (int num : nums) {xorSum ^= num;}int diffBit = xorSum & -xorSum; // 找到最右邊的不同位int[] result = new int[2];for (int num : nums) {if ((num & diffBit) == 0) {result[0] ^= num;} else {result[1] ^= num;}}return result;
}

二進制數1

牛客網 ： 二進制數1

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;public class Main{public static void main(String[] args) throws IOException {BufferedReader br=new BufferedReader(new InputStreamReader(System.in));long lnum=Long.parseLong(br.readLine());br.close();System.out.println(Long.bitCount(lnum));}
}

二進制不同位數

牛客網 ： 二進制不同位數

import java.io.*;
import java.util.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));String s = null;while ((s = reader.readLine()) != null) {String[] cs = s.split(" ");//int n = Integer.parseInt(s);//異或，相同是0，不同是1,先異或，再統計1的個數int a = Integer.parseInt(cs[0]);int b = Integer.parseInt(cs[1]);int c = a ^ b;int res=0;while (c!=0){res+=c&1;c=c>>>1;}System.out.println(res);}}}