Labuladong’s algorithm cheat sheet; This article is only for self-sorting, the original chain as above

[TOC]

One, letter conversion case, case reversal (bit operation)

Turn to lowercase char | = ‘ ‘; Uppercase char &= ‘_’; Char ^= “;

A given string: zHaNSanKoiNIAHoinoiSAIODoijoIni

Result output:

// Case needs to be reversed
reverse:ZhAnsANkOIniahOINOIsaiodOIJOiNI
/ / all uppercase
toUpperCase:ZHANSANKOINIAHOINOISAIODOIJOINI
/ / all lowercase
toLowerCase:zhansankoiniahoinoisaiodoijoini
Copy the code

Code examples:

/ * * * lowercase char | = ' '; * uppercase char &= '_'; * case reversal char ^= "; * /
@Test
public void testY(a) {
    String s = "zHaNSanKoiNIAHoinoiSAIODoijoIni";
    char[] result = new char[s.length()];
    int i=0;
    for(char tmp : s.toCharArray()) {
        tmp ^= ' ';
        result[i++] = tmp;
    }
    System.out.println("reverse:" + new String(result));

    i = 0;
    for(char tmp : s.toCharArray()) {
        tmp &= '_';
        result[i++] = tmp;
    }
    System.out.println("toUpperCase:" + new String(result));


    i = 0;
    for(char tmp : s.toCharArray()) {
        tmp |= ' ';
        result[i++] = tmp;
    }
    System.out.println("toLowerCase:" + new String(result));
}
Copy the code

Two, judge whether two numbers are different signs (bit operation)

X ^y<0 x^y<0 x^y<0 x^y

Note: 0 complement indicates only one kind, 0 is neither positive nor negative, there is no +0, -0; If a judgment is imposed, the sign bit of 0 in the complement is 0 and belongs to a positive number.

/** * two cases of 0 */
@Test
public void testJudgeTwoNums(a) {
    int x = -0, y = 2, a = 0, b = -2;
    System.out.println((x^y)<0); // false
    System.out.println((a^b)<0); // true
}
Copy the code

Swap two numbers without using temporary variables

int a = 1, b = 2;
a ^= b;
b ^= a;
a ^= b;
Copy the code

Eliminate the last 1 in the binary representation of a number

n&(n-1)

  1. Calculate hamming weights

    @Test
public void hammingWeight(a) {
int n = 8;
int res = 0;
while(n ! =0) {
    n = n & (n - 1);
    res++;
}
System.out.println("Number of 1s in binary res:" + res);
}
Copy the code

  2. Determine if a number is an exponent of 2 (the exponent binary representation of 2 contains only one 1)

    boolean isPowerOfTwo(int n) {
    if (n <= 0) return false;
    return (n & (n - 1)) = =0;
}
Copy the code

Query for elements that occur only once

a ^ a = 0 ; a ^ 0 = a

// Given a non-null positive array, find the element that appears only once except for one element that appears only once
int singleNumber(int[] nums) {
    int res = 0;
    for (int n : nums) {
        res ^= n;
    }
    return res;
}
Copy the code