Non-negative Integers without Consecutive Ones LeetCode solution in Java

1
class Solution {
2
  public int findIntegers(int n) {
3
    int val = 0, res = 0, cn = n, digi = 0, prevdig = 0, i; // digi means bin digi
4
    while (cn > 0) {
5
      cn = cn >> 1;
6
      digi++;
7
    }
8
    int dp[] = new int[digi + 1];
9
    dp[0] = 1;
10
    dp[1] = 2;
11
    for (i = 2; i <= digi; i++) dp[i] = dp[i - 1] + dp[i - 2];
12
    digi++;
13
    while (digi-- >= 0) {
14
      if ((n & (1 << digi)) > 0) {
15
        res += dp[digi];
16
        if (prevdig == 1) return res;
17
        prevdig = 1;
18
      } else prevdig = 0;
19
    }
20

21
    return res + 1;
22
  }
23
}