CODEWITHSUNDEEP
javacountbit
vader69
vader69

Reputation: 27

Finding the number of bits required to save int number

So my problem is that i have to recursively find the number of bits, that are required to display / save a number e.g. 4(10)=100(2) so 3 bits would be needed. I think i already know how i am supposed to do it, but my code still doesnt work. Here is what i have so far: 

public static int l = 1;
    public static int countUsedBits(long z) {
        if (z == 0) {
            return l;
        } else {
            ++l;
            return countUsedBits(log, z >>> 1);
        }
    }

The problem is that the returned number is always 1 off (too big) of the correct number. Thanks for any help in advance!

Upvotes: 1

Views: 365

Answers (1)

WJS
WJS

Reputation: 40054

The number of bits required to representN in binary is log base 2 of N, referred to a log2 N. Once you get the result, round up, even if the result is integral.

Examples.

  1. log2 of 4 = 2. add 1 and get 3. so 4 requires 3 bits
  2. log2 of 8 = 3. add 1 and get 4. so 8 requires 4 bits.

Note that above, anything between 4 and 7 inclusive, requires 3 bits.

Just remember than a logarithm is basically an exponent. So when you have for a given base of 2 then the result of log2 N is the exponent such that 2^result = N (in this case, ^ means raise to that power).

EDIT:

You're answer was real close. Set l = 0 initially and then return l when z == 0. it should work. And your recursive call should not include anything other than z>>>1.

Note: One problem with your method is that you need to keep resetting l for each call and that is not user friendly. So another way which does not require a separate value is to do the following:

   public static int countUsedBits(long z) {
      if (z == 0) {
         return 0;
      }
      return countUsedBits(z >>> 1) + 1;
   }

I recommend you put in some print statement to see how this progresses.

Upvotes: 1

Related Questions