int count = 0;
while (n != 0) {
    n = n & (n - 1);
    count++;

}

n & 1    // 判断奇偶

~x = -x - 1

(n & 1) == 0  // 偶数

lowbit = n & (-n);

n = 12 = 1100  
-n = 0100  
结果 = 0100

n = n & (n - 1);

((n >> k) & 1) == 1

n = n | (1 << k);

n = n & ~(1 << k);

n = n ^ (1 << k);

int mask = 0;
for (char c : s.toCharArray()) {
    mask ^= (1 << (c - 'a'));
}

result = (result << shift) | x;

int A = 6;  // 二进制: 110
int B = 5;  // 二进制: 101

// 获取 B 的二进制长度
int lenB = Integer.toBinaryString(B).length();  // lenB = 3

// 方法1：使用数学公式
int result1 = A * (int)Math.pow(2, lenB) + B;  // 6 * 8 + 5 = 53

// 方法2：使用位运算
int result2 = (A << lenB) | B;  // (110 << 3) | 101 = 110000 | 101 = 110101

System.out.println("A: " + Integer.toBinaryString(A));      // 110
System.out.println("B: " + Integer.toBinaryString(B));      // 101
System.out.println("拼接结果: " + Integer.toBinaryString(result2));  // 110101
System.out.println("十进制: " + result2);  // 53

n      = 8  = 1000  (二进制)
n - 1  = 7  = 0111
n & (n-1) = 1000 & 0111 = 0000 = 0

class Solution {
    private static final int MOD = 1000000007;

    public int concatenatedBinary(int n) {
        long result = 0;
        int shift = 0;  // 移位数
        for (int i = 1; i <= n; i++) {
            // 判断一个数是否为2的幂
            if ((i & (i - 1)) == 0) {
                shift++;
            }
            result = ((result << shift) | i) % MOD;
        }
        return (int) result;
    }
}

prefix[i] = nums[0] + nums[1] + ... + nums[i-1]

sum[left, right] = prefix[right+1] - prefix[left]

class Main{
    // 求区间[x,y]之和
    public int PrefixSum1D(int[] nums, int x, int y){
        int n = nums.length;

        // 构建前缀和数组
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        return query(prefix ,x, y);
    }
    // 查询区间[left, right]的和
    public int query(int[] prefix, int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
}

public class Main {
    // 求二维数组从 (row1, col1) 到 (row2, col2) 的元素之和
    public int PrefixSum2D(int[][] matrix, int row1, int col1, int row2, int col2) {
        int m = matrix.length, n = matrix[0].length;
        int[][] prefix = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefix[i + 1][j + 1] = matrix[i][j]
                        + prefix[i][j + 1]
                        + prefix[i + 1][j]
                        - prefix[i][j];
            }
        }
        return query(prefix, row1, col1, row2, col2);
    }
    // 通过前缀和数组查询指定区域的元素之和
    public int query(int[][] prefix ,int row1, int col1, int row2, int col2) {
        return prefix[row2 + 1][col2 + 1]
                - prefix[row1][col2 + 1]
                - prefix[row2 + 1][col1]
                + prefix[row1][col1];
    }
}

diff[i] = a[i] - a[i-1]  (i ≥ 1)
diff[0] = a[0]

diff[l] += val
diff[r+1] -= val

diff[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]

子矩阵修改 对(x1,y1)到(x2,y2)加上val
diff[x1][y1] += val
diff[x2+1][y1] -= val
diff[x1][y2+1] -= val
diff[x2+1][y2+1] += val

public class Main {
    // 求数组的差分数组
    public int[] Diff(int[] nums) {
        int n = nums.length;
        int[] diff = new int[n];
        diff[0] = nums[0];
        for (int i = 0; i < n; i++) {
            diff[i] = diff[i + 1] - nums[i];
        }
        return diff;
    }
}

class Solution {
    // 在长度为 k 的所有子数组中，求最大和
    public int fixedWindow(int[] nums, int k) {
        int n = nums.length;
        int sum = 0;

        // 初始化第一个窗口
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        int ans = sum;

        // 窗口滑动
        for (int i = k; i < n; i++) {
            sum += nums[i];
            sum -= nums[i - k];
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}

class Solution {
    // 求和 >= target 的最短子数组长度
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int left = 0, sum = 0;
        int ans = Integer.MAX_VALUE;

        for (int right = 0; right < n; right++) {
            sum += nums[right];
            while (sum >= target) {
                ans = Math.min(ans, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

class Solution {
    // 返回每个元素右侧第一个更大的元素
    public int[] nextGreater(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                int idx = stack.pop();
                res[idx] = nums[i];
            }
            stack.push(i);
        }
        return res;
    }
}

// 求一个数组的所有子集  
class Solution {  
    List<List<Integer>> res = new ArrayList<>();  
    List<Integer> path = new ArrayList<>();  
  
    public List<List<Integer>> subsets(int[] nums) {  
        backtrack(nums, 0);  
        return res;  
    }     
    // 回溯算法  
    private void backtrack(int[] nums, int start) {  
        res.add(new ArrayList<>(path));  
  
        for (int i = start; i < nums.length; i++) {  
            path.add(nums[i]);  
            backtrack(nums, i + 1);  
            path.remove(path.size() - 1);  
        }  
    }  
}

void dfs(int node) {
    visited[node] = true;
    for (int next : graph[node]) {
        if (!visited[next]) {
            dfs(next);
        }
    }
}

void bfs(int start) {
    Queue<Integer> queue = new ArrayDeque<>();
    queue.offer(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int cur = queue.poll();
        for (int next : graph[cur]) {
            if (!visited[next]) {
                visited[next] = true;
                queue.offer(next);
            }
        }
    }
}

class Solution {
    public int knapsack01(int[] w, int[] v, int bag) {
        int n = w.length;
        int[] dp = new int[bag + 1];

        for (int i = 0; i < n; i++) {
            for (int j = bag; j >= w[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
        return dp[bag];
    }
}

class Solution {
    public int completeKnapsack(int[] w, int[] v, int bag) {
        int n = w.length;
        int[] dp = new int[bag + 1];

        for (int i = 0; i < n; i++) {
            for (int j = w[i]; j <= bag; j++) {
                dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
        return dp[bag];
    }
}

val = (val << 1) | root.val;

1 -> 0 -> 1

val = 0

// 第一个节点: root.val = 1
val = (0 << 1) | 1
    = 0 | 1
    = 1   // 二进制: 1

// 第二个节点: root.val = 0
val = (1 << 1) | 0
    = 2 | 0
    = 2   // 二进制: 10

// 第三个节点: root.val = 1
val = (2 << 1) | 1
    = 4 | 1
    = 5   // 二进制: 101

class TreeNode{
    int val;
    TreeNode left, right;
    TreeNode() {};
    TreeNode(int val){
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class HanoiTower{
    public void move(int n, char from, char to, char aux){
        if (n == 1){
            System.out.println("Move disk 1 from " + from + " to " + to);
            return;
        }
        move(n-1, from, aux, to);
        System.out.println("Move disk " + n + " from " + from + " to " + to);
        move(n-1, aux, to, from);
    }
}

class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root.left == null && root.right == null) return true;
        
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private boolean isValidBST(TreeNode root, long min, long max) {
        if (root == null) return true;
        if (root.val <= min || root.val >= max) return false;
        return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
    }
}

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        inorder(root, ans);
        return ans;
    }
    private void inorder(TreeNode node, List<Integer> res){
        if (node == null){
            return;
        }
        inorder(node.left, res);
        res.add(node.val);
        inorder(node.right, res);
    }
}

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        else if (root.left == null && root.right == null) return 1;
        else {
            int leftDepth = maxDepth(root.left);
            int rightDepth = maxDepth(root.right);
            return Math.max(leftDepth, rightDepth) + 1;
        }
    }
}

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null)   return null;
        TreeNode l = invertTree(root.left);
        TreeNode r = invertTree(root.right);
        root.left = r;
        root.right = l;
        return root;
    }
}

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root.left, root.right);
    }

    private boolean check(TreeNode p, TreeNode q){
        if(p == null && q == null)    return true;
        if(p == null || q == null)    return false;
        return p.val == q.val && check(p.left,q.right) && check(p.right, q.left);
    }
}

class Solution {
    public int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return ans;
    }
    private int dfs(TreeNode node){
        if(node == null){
            return -1;
        }
        int l = dfs(node.left) + 1;
        int r = dfs(node.right) + 1;
        ans = Math.max(l + r, ans);
        return Math.max(l,r);
    }
}

class TreeNode{
    int val;
    TreeNode left, right;
    TreeNode() {};
    TreeNode(int val){
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        else if (root.left == null && root.right == null) return 1;
        else {
            int leftDepth = maxDepth(root.left);
            int rightDepth = maxDepth(root.right);
            return Math.max(leftDepth, rightDepth) + 1;
        }
    }
}

class Solution{
    int ans = 0;

    private void dfs(TreeNode root, int depth){
        if (root == null) return;
        depth++;
        if (root.left == null && root.right == null){
            ans = Math.max(ans, depth);
        }
        dfs(root.left, depth);
        dfs(root.right, depth);
    }

    public int maxDepth(TreeNode root) {
        dfs(root, 0);
        return ans;
    }
}

class TreeNode{
    int val;
    TreeNode left, right;
    TreeNode() {};
    TreeNode(int val){
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Recursion {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        inorder(root, ans);
        return ans;
    }
    private void preorder(TreeNode node, List<Integer> res){
        if (node == null){
            return;
        }
        inorder(node.left, res);
        res.add(node.val);
        inorder(node.right, res);
    }
}

class Iteration {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            // 一路向左
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            // 弹出栈顶（最左节点）
            curr = stack.pop();
            ans.add(curr.val);      // 访问
            curr = curr.right;      // 转向右子树
        }
        return ans;
    }
}

class Mirris {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left == null) {
                ans.add(curr.val);
                curr = curr.right;
            } else {
                // 找到左子树的最右节点（前驱）
                TreeNode pre = curr.left;
                while (pre.right != null && pre.right != curr) {
                    pre = pre.right;
                }
                if (pre.right == null) {
                    // 建立线索
                    pre.right = curr;
                    curr = curr.left;
                } else {
                    // 线索已存在，说明左子树已遍历完
                    pre.right = null; // 恢复树结构
                    ans.add(curr.val);
                    curr = curr.right;
                }
            }
        }
        return ans;
    }
}

public class Main {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);

        Recursion recursion = new Recursion();
        List<Integer> res1 = recursion.inorderTraversal(root);
        System.out.println("Recursion: " + res1);

        Iteration iteration = new Iteration();
        List<Integer> res2 = iteration.inorderTraversal(root);
        System.out.println("Iteration: " + res2);

        Mirris mirris = new Mirris();
        List<Integer> res3 = mirris.inorderTraversal(root);
        System.out.println("Mirris: " + res3);
    }
}

1
 \
  2
 /
3

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);

int sum = list.stream()
        .filter(x -> x % 2 == 0)
        .map(x -> x * x)
        .reduce(0, Integer::sum);

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode p = head;
        ListNode q = head;
        while(q != null && q.next != null){
            p = p.next;
            q = q.next.next;
        }
        return p;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode q = head;
        while(q != null){
            ListNode nxt = q.next;
            q.next = pre;
            pre = q;
            q = nxt;
        }
        return pre;
    }
}

class Solution {
    public boolean isPalindrome(ListNode head) {
        // 快慢指针
        ListNode fast =head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        // 反转
        ListNode pre = null;
        ListNode cur = slow;
        while (cur != null) {
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }

        while (pre != null){
            if(pre.val != head.val){
                return false;
            }
            head = head.next;
            pre = pre.next;
        }
        return true;
    }
}

class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0 || x > 0 && x % 10 == 0){
            return false;
        }
        int rev = 0;
        while(rev < x / 10){
            rev = rev * 10 + x % 10;
            x /= 10;
        }
        return rev == x || rev == x / 10;
    }
}

class Solution {
    public void reorderList(ListNode head) {
        ListNode mid = middle(head);
        ListNode head2 = reverse(mid);
        while(head2.next != null){
            ListNode nxt = head.next;
            ListNode nxt2 = head2.next;
            head.next = head2;
            head2.next = nxt;
            head = nxt;
            head2 = nxt2;
        }
    }

    private ListNode reverse(ListNode head){
        ListNode pre = null, cur = head;
        while(cur != null){
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }

    private ListNode middle(ListNode head){
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode cur = dummy;
        while(cur.next != null ){
            if(cur.next.val == val){
                cur.next = cur.next.next;
            }
            else{
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode node0 = dummy;
        ListNode node1 = head;
        while (node1 != null && node1.next != null) {
            ListNode node2 = node1.next;
            ListNode node3 = node2.next;

            node0.next = node2; // 0 -> 2
            node2.next = node1; // 2 -> 1
            node1.next = node3; // 1 -> 3

            node0 = node1;
            node1 = node3;
        }
        return dummy.next;
    }
}

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode node1 = head;
        ListNode node2 = head.next;
        ListNode node3 = node2.next;

        node1.next = swapPairs(node3);
        node2.next = node1;

        return node2;
    }
}