力のボタンのアルゴリズムは題の日記の《位の演算》01をします

目次

1.数字を0にする操作回数

2.バイナリチェーンテーブル回転整数

3.バイナリ1の個数

4.最大値

5.数字の補数

6. ペア交換

7.デジタルバイナリの下の1の数に基づいて

をソートする.

8.一度しか現れない数字

9.異なる

を探します

10.欠落した数字

11.交互ビット2進数

12.逆バイナリ

13.2つの整数の和

14.整数変換

15.4のべき乗

16.2のべき乗

17.反転数ビット

18.数字を16進数

に変換

次のアルゴリズムの問題はleetCode問題ライブラリから来ています.https://leetcode-cn.com/本編の難易度は簡単です
1.数字を0にする操作回数
非負の整数numをあげます.0にするために必要なステップ数を返してください.現在の数字が偶数であれば、それを2で割る必要があります.そうでなければ、1を減算します.

class Solution {
     
       //    0     ，    2，    1
    public int numberOfSteps (int number) {
     
        if (number == 0) return 0;
        return zeroNextValue(number, 0);
    }

    //      1     
    private int zeroNextValue(int number, int step) {
     
        if (number == 0) return step;
        if ((number & 1) != 0) {
     
            step++;
            return zeroNextValue(number - 1, step);
        } else {
     
            step++;
            return zeroNextValue(number >> 1, step);
        }
    }
}

考え方:バイナリの末尾が1のは奇数で、0のは偶数です
2.バイナリチェーンテーブル回転整数
単一チェーンテーブルの参照ノードheadをあげます.チェーンテーブルの各ノードの値は0ではなく1です.このチェーンテーブルは整数値のバイナリ表現であることが知られています.チェーンテーブルに表示されている数字の10進数値を返してください.

// Definition for singly-linked list.
public class ListNode {
     
        int val;
        ListNode next;

        ListNode(int x) {
     
            val = x;
        }
 }

class Solution {
     
    public int getDecimalValue(ListNode head) {
     
       int val = head.val;
        while (head.next != null) {
     
            head = head.next;
            //         2,    1             
            val = head.val == 0 ? val << 1 : (val << 1) | 1;
        }
        return val;
    }
}

構想:チェーンテーブルと構造のバイナリ表現数を構築する
3.バイナリの1の個数
関数を実装して、整数を入力して、その数のバイナリ表現の中の1の数を出力してください.例えば、9をバイナリが1001、2ビットが1と表す.したがって、9が入力されると、関数は2を出力する.

public class Solution {
     
    //   32       ，      
    public int hammingWeight(int number) {
     
        int count = 0;
        for (int i = 0; i < 32; i++) {
     
            if ((number & 1 << i ) != 0) count++;
        }
        return count; 
    }
}

考え方:整数の位置ごとに1かどうかの判断を行う
4.最大値
2つの数字aとbの中で最大の方法を作成します.if-elseまたはその他の比較演算子は使用できません.

public class Solution {
     
     public int maximum(int a, int b) {
     
        //  1   ， ab ,             ，  int     
        //        ，long 64 ，int 32 
        int val = ((int)(((long)a - (long)b) >> 63)) & 1;
        return a + (b - a) * val;
    }
}

考え方:差分値をとり、符号ビットから大きさ値を判断する
5.数字の補数
正の整数を指定し、その補数を出力します.補数はその数のバイナリ表現に対して逆をとる.

 public int findComplement(int num) {
     
         int origin = num;
        int val = 0;
        //      ，  0  ，            
        //        1    ，      
        while (num > 0) {
     
            num = num >> 1;
            val = val == 0 ? 1 : (val << 1) | 1;
        }
        return origin ^ val;
    }

構想:整数の1の最高位を探して、同長の全1バイナリと異或演算を行います
6.ペアリング交換
ペアリング交換.プログラムを作成し、ある整数の奇数ビットと偶数ビットを交換し、できるだけ少ない命令を使用する(すなわち、ビット0とビット1が交換され、ビット2とビット3が交換され、このように推定する)

	  //10101010101010101010101010101010 = 0xaaaaaaaa
      //01010101010101010101010101010101 = 0x55555555
      public int exchangeBits(int num) {
     
        return (num << 1 & 0xaaaaaaaa) | (num >> 1& 0x55555555);
      }

考え方:左右に1つずつシフトし、最後の結果を重ねる
7.数値バイナリの下の1の数でソート
整数配列arrをあげます.配列の要素を2進数で表す数字1の数に従って昇順に並べ替えてください.複数のデジタルバイナリの1の数が同じである場合は、数値サイズの昇順に並べ替える必要があります.ソート後の配列を返してください.

 public int[] sortByBits(int[] arr) {
     
        Integer integers[] = new Integer[arr.length];
        for (int i = 0; i < arr.length; i++) {
     
            integers[i] = new Integer(arr[i]);
        }
        Arrays.sort(integers, new Comparator<Integer>() {
     
            @Override
            public int compare(Integer o1, Integer o2) {
     
                int bitCount1 = Integer.bitCount(o1);
                int bitCount2 = Integer.bitCount(o2);
                if (bitCount1 == bitCount2) {
     
                    return o1 - o2;
                }
                return bitCount1 - bitCount2;
            }
        });

        int[] result = new int[integers.length];
        for (int i = 0; i < integers.length; i++) {
     
            result[i] = integers[i].intValue();
        }
        return result;
    }

構想:比較器を用いてIntegerを比較する.bitCount()メソッドはバイナリ1の個数を返します
8.一度しか出てこない数字
空でない整数配列が与えられ、ある要素が1回しか現れない以外は、各要素が2回現れます.それが一度しか現れなかった要素を見つけます.

public int singleNumber(int[] nums) {
     
        int result = 0;
        for (int item : nums) {
     
            result ^= item;
        }
        return result;
    }

構想:異或演算と演算に参加する2つの数の位置は関係ない.任意の数と0は、その数自体に等しいか、または等しい.2つの同じ数値の異和演算は0に等しい
9.違いを探す
2つの文字列sおよびtが与えられ、それらは小文字のみを含む.文字列tは、文字列sによってランダムに並べ替えられ、ランダムな位置にアルファベットが追加される.tに追加されたアルファベットを見つけてください.

   public char findTheDifference(String s, String t) {
     
        char res = 0 ;
        char[] chars = s.toCharArray();
        char[] chart = t.toCharArray();
        for (char item : chart) {
     
            res ^= item;
        }
        for (char item : chars) {
     
            res ^= item;
        }
        return  res;
    }

考え方:問題8の考え方と同じで、異あるいは2つの同じ数は0に等しくて、最終的に残ったのは多く出てきたのです
10.欠落した数値
0,1,2,...,nのn個の数を含むシーケンスを与え,0...nの中にシーケンスに現れない数を探し出す.

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

考え方:同上
11.交互ビットバイナリ数
正の整数を与えて、彼が交互ビットのバイナリ数であるかどうかをチェックします.言い換えれば、彼のバイナリ数が隣接する2つのビット数は等しくありません.

 public boolean hasAlternatingBits(int n) {
     
      int temp = n ^ (n >> 1);
      return (temp & (temp + 1)) == 0;
}

考え方:交互ビットマージが正しい場合は全1のバイナリを構成します
12.逆バイナリビット
与えられた32ビットの符号なし整数のバイナリビットを逆にします.

 public int reverseBits(int n) {
     
        int result = 0;
        for (int i = 0; i < 32; i++) {
     
            int last = n & 1;
            result = result << 1 | last;
            n = n >>> 1;
        }
        return result;
    }

考え方:逆変位出力
13.両整数の和
演算子+と-を使用しないで、2つの整数a、bの和を計算します.

 public int getSum(int a, int b) {
     
 	if (b == 0) return a;
        int temp = (a & b) << 1;   //          +1   
        int resultTemp = a ^ b;
        return getSum(resultTemp, temp);
    }

考え方:キャリー位置を算出し、キャリーがないまでループを繰り返す
14.整数変換
整数変換整数Aを整数Bに変換するには、いくつかのビットを変更する必要があることを決定する関数を記述します.

public int convertInteger(int A, int B) {
     
  	    int count = 0;
        for (int i = 0; i < 32; i++) {
     
            if (((1 & A) ^ (1 & B)) == 1) count++;
            A = A >> 1;
            B = B >> 1;
        }
        return count;
    }

考え方:各位置の違いを比較する
15.4のべき乗
整数(32ビットの符号付き整数)を指定し、4のべき乗次数であるかどうかを判断する関数を作成します.

   public boolean isPowerOfFour(int num) {
     
    if (num == 1) return true;
        if (num < 0 || (num & (num - 1)) != 0) return false;
        return (num & 0x55555555) != 0;
    }

考え方:4のバイナリは100、100,000,000,000,000を前に押すといずれも4のべき乗であり、末尾を除いて奇数ビットは1であり、1ビットが1のバイナリ数だけが4のべき乗であり、同時に4の0次べき乗1 4-1=3=011、16-1=15=1111、64-1=63=111111
16.2のべき乗
整数を指定し、関数を作成して2のべき乗次数であるかどうかを判断します.

 public boolean isPowerOfTwo(int num) {
     
            if (num <= 0 || (num & (num - 1)) != 0) return false;
        return (num & 1) == 0 || num == 1;
    }

考え方:同じ問題で、ただ2のべき乗は末尾を除いて1人だけが1のバイナリ数です
17.反転数位
32ビットの整数numを指定すると、1つのビットを0から1に変更できます.プログラムを作成して、あなたが得ることができる最も長い一連の1の長さを見つけてください.

   public int reverseBits(int num) {
     
        int preCount = 0;
        int tempCount = 0;
        int result = 0;

        for (int i = 0; i < 32; i++) {
     
            if ((num & 1<< i) != 0) {
     
                preCount++;
            } else {
     
                result = Math.max(result, preCount + tempCount + 1);
                tempCount = preCount;
                preCount = 0;
            }
        }
        return Math.max(result, preCount + tempCount + 1);
    }

考え方:1.統計1の連続個数2.最初の1でないバイナリビットに遭遇した場合、前回の値を保存し、前の値を空にします.このときの最大長を同時に計算する
18.数字を16進数に変換する
整数を指定し、アルゴリズムを記述してこの数を16進数に変換します.負の整数については,通常,符号化演算法を用いる.注意:1.16進数のすべてのアルファベット(a-f)は小文字でなければなりません.2.16進数文字列に余分な先頭ゼロを含めることはできません.変換する数が0の場合、単一の文字’0’で表される.その他の場合、16進数文字列の最初の文字は0文字ではありません.3.与えられた数は32ビットの符号付き整数の範囲内であることを保証する.4.ライブラリから提供された数値を直接変換またはフォーマットすることはできません.

  public String toHex(int num) {
     
   if (num == 0) return "0";
        int compare = 0xf;  //0xf
        char regex[] = new char[]{
     '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
        StringBuilder sb = new StringBuilder();
        while (num != 0 && sb.length() < 8) {
     
            int temp = num & compare;
            sb.append(regex[temp]);
            num >>= 4;
        }
        return sb.reverse().toString();

    }

考え方:バイナリ4ビット対応16進数の1ビット