ビット操作 Counting Bits

問題文

整数 n を指定すると、各 i (0 <= i <= n) について、ans[i] が i のバイナリ表現における 1 の数となる、長さ n + 1 の配列 ans を返します。

解答①

引数n+1の長さを持つ配列ansを用意し、ans.length分をループします。
(i/2)+(i%2)で2進数変換を行い、1のカウント数をansに格納する。

コード

class Solution {
    public int[] countBits(int n) {
        int offset=1;
        int [] ans = new int [n+1];
        for (int i=1;i < ans.length;i++){
            ans[i]=ans[i/2]+(i%2);
        }
        return ans;
    }
}

実行時間：2ms
メモリー：46.55MB

解答②

n&(n-1)により、nの最下位の1を0に変換および論理積を行い、ans[i]を求めます。

コード

class Solution {
    public int[] countBits(int n) {
        int [] ans = new int [n+1];
        for (int i=1;i < ans.length;i++){
            ans[i]=ans[i&(i-1)]+1;
        }
        return ans;
    }
}

実行時間:2ms
メモリー：46.78MB

参考
https://www.madopro.net/entry/2016/09/23/223037
https://qiita.com/KueharX/items/98dcdb1b82d39c464a92