Bit manipulation - Find next higher sparse number

30 March 2015

Problem overview

This is a good mental exercise and an interesting bit manipulation problem for practicing binary related logic:

an integer is a sparse number if there are no adjacent 1 in it's binary representation. - 5 --> 101 (no adjacent 1s) - 9 --> 1001 (no adjacent 1s) - 6 --> 110 is not sparse number.

Now you are given an integer N find the NEXT HIGHER sparse number of N.

Algorithm analysis

There are 2 possible number types you are going to deal with: 1. already sparse number 2. non-sparse number

Algorithm for solution based on the 2 scenarios:

  1. Check if binary representation of number is Sparse, if it is:

  2. Check if bin. number contains a sequence of at least 2 zeros: (i.e "xx1100xx" or "xx11001xx") this will enable for fitting a 1 just right at index of first 0 found and setting to 0 all the right remaining bits (i.e"1010010" to "1010100"). If index of first 2 zeros is 0, just return n+1, i.e"10100" to "10101").

-If it doesn't contain a seq. of 2 zeros shift N left of 1 and set all remaining bits to 0, return next higher power of 2. i.e"10101", "100000")

  1. If number is not sparse:

  2. Check for highest index of a sequence of at least 2 ones (i.e "10011010001" - index 6) then we will see if we can put a 1 at starting index after sequence and set remaining bits to zero on the right side. (i.e: "10011010001" to "10100000000") If we find out we created a new seq. of 2 one's on that index (i.e: "10110010001" to "11000000000") then we keep flipping bits to 0 until we get to a point where previous bit is 0 and next is 1 (i.e "101xx") which is sparse, or 0.

  3. If we get 0 then we just need to left shift 1 by the original number's length, example: "110010010" to "1000000000" (512). - Next power of 2.

Implementation

Below is the algorithm implementation that translates the idea above:

public class Solution {
public static void main(String args[]) {
    int n = 72;
    System.out.println(convertToBinaryString(n));
    int nextSparse = getNextBiggerSparseNumber(n);
    System.out.println(nextSparse);
    System.out.println(convertToBinaryString(nextSparse));

}



public static int getNextBiggerSparseNumber(int n) {
    if(isSparseBinaryNumber(n)) {
        int i = getFirstIndexSeqZeros(n);
        if (i != -1) {
            if (i - 1 == 0) {
                return n + 1;
            }



        <span class="k">return</span> <span class="nf">incrementToNextSparseFromZeroIndex</span><span class="o">(</span><span class="n">n</span><span class="o">,</span> <span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="o">);</span>

    <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
        <span class="k">return</span> <span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="n">getLengthBits</span><span class="o">(</span><span class="n">n</span><span class="o">);</span>
    <span class="o">}</span>
<span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
    <span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">getLastIndexSeqOnes</span><span class="o">(</span><span class="n">n</span><span class="o">);</span>           
    <span class="k">return</span> <span class="nf">incrementToNextSparseFromIndex</span><span class="o">(</span><span class="n">n</span><span class="o">,</span> <span class="n">i</span><span class="o">);</span>          
<span class="o">}</span>




}



/*
 * Sets the bit at index to 1 while setting all remaining bits on the right to 0, "1001101" index 4 -> "1010000"
 * @param n
 * @param index
 * @return
 /
public static int incrementToNextSparseFromZeroIndex(int n, int index) {
    int i = index - 1; 

    int n2 = n;
    n2 = setBit(n2, index, true);
    while(i >= 0) {
        n2 = setBit(n2, i, false);
        i--;        

    }
    return n2;
}



/*
 * Sets all bits of n to 0 until index, from right to left, then sets next bit index+1 to 1 and checks next bit,
 * if next is 1 or if number is lower than original n, keeps setting last bit to 0 and current to 1, from right
 * to left until a valid condition for sparse number is reached, otherwise if it reaches 0 returns next power of
 * 2. (1 << sizeOf(n))
 *

 * @param n
 * @param index
 * @return
 /
public static int incrementToNextSparseFromIndex(int n, int index) {
    int i = 0;
    int n2 = n;
    boolean prev = false, current = false;



<span class="k">while</span><span class="o">(</span><span class="n">i</span> <span class="o">&lt;=</span> <span class="n">index</span><span class="o">)</span> <span class="o">{</span>
    <span class="n">n2</span> <span class="o">=</span> <span class="n">setBit</span><span class="o">(</span><span class="n">n2</span><span class="o">,</span> <span class="n">i</span><span class="o">,</span> <span class="kc">false</span><span class="o">);</span>
    <span class="n">i</span><span class="o">++;</span>          
<span class="o">}</span>
<span class="n">n2</span> <span class="o">=</span> <span class="n">setBit</span><span class="o">(</span><span class="n">n2</span><span class="o">,</span>  <span class="n">i</span><span class="o">,</span> <span class="kc">true</span><span class="o">);</span>
<span class="n">prev</span> <span class="o">=</span> <span class="kc">true</span><span class="o">;</span>
<span class="n">i</span><span class="o">++;</span>
<span class="n">current</span> <span class="o">=</span> <span class="n">getBit</span><span class="o">(</span><span class="n">n2</span><span class="o">,</span>  <span class="n">i</span><span class="o">);</span>

<span class="k">while</span> <span class="o">(</span><span class="n">current</span> <span class="o">&amp;&amp;</span> <span class="n">prev</span> <span class="o">&amp;&amp;</span> <span class="n">n2</span> <span class="o">&gt;</span> <span class="mi">0</span> <span class="o">||</span> <span class="o">(</span><span class="n">n2</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="o">&amp;&amp;</span> <span class="n">n2</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="o">))</span> <span class="o">{</span>
    <span class="n">n2</span> <span class="o">=</span> <span class="n">setBit</span><span class="o">(</span><span class="n">n2</span><span class="o">,</span> <span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="o">,</span> <span class="kc">false</span><span class="o">);</span>
    <span class="n">n2</span> <span class="o">=</span> <span class="n">setBit</span><span class="o">(</span><span class="n">n2</span><span class="o">,</span> <span class="n">i</span><span class="o">,</span> <span class="kc">true</span><span class="o">);</span>
    <span class="n">i</span><span class="o">++;</span>      
    <span class="n">prev</span> <span class="o">=</span> <span class="n">current</span><span class="o">;</span>
    <span class="n">current</span> <span class="o">=</span> <span class="n">getBit</span><span class="o">(</span><span class="n">n2</span><span class="o">,</span>  <span class="n">i</span><span class="o">);</span>
<span class="o">}</span>
<span class="k">if</span> <span class="o">(</span><span class="n">n2</span> <span class="o">==</span> <span class="mi">0</span><span class="o">)</span> <span class="o">{</span>
    <span class="k">return</span> <span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="n">getLengthBits</span><span class="o">(</span><span class="n">n</span><span class="o">);</span>
<span class="o">}</span>

<span class="k">return</span> <span class="n">n2</span><span class="o">;</span>




}



/*
 * Checks index of first seq. of 2 consecutive zeros. i.e: "1001 -> index = 2"
 * if no seq. found return -1
 *
 * @param n
 * @return
 /
public static int getFirstIndexSeqZeros(int n) {
    // current and previous bit if set to 0 then true
    boolean cur, prev = false;



<span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
<span class="k">while</span><span class="o">(</span><span class="n">n</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="o">)</span> <span class="o">{</span>
  <span class="k">if</span> <span class="o">(</span> <span class="o">(</span><span class="n">n</span> <span class="o">&amp;</span> <span class="mi">1</span><span class="o">)</span> <span class="o">==</span> <span class="mi">0</span><span class="o">)</span> <span class="o">{</span>
    <span class="n">cur</span> <span class="o">=</span> <span class="kc">true</span><span class="o">;</span>
  <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
    <span class="n">cur</span> <span class="o">=</span> <span class="kc">false</span><span class="o">;</span>
  <span class="o">}</span>
  <span class="k">if</span> <span class="o">(</span><span class="n">cur</span> <span class="o">&amp;&amp;</span> <span class="n">prev</span><span class="o">)</span> <span class="o">{</span>
      <span class="k">return</span> <span class="n">i</span><span class="o">;</span>
  <span class="o">}</span>
  <span class="n">prev</span> <span class="o">=</span> <span class="n">cur</span><span class="o">;</span> 

  <span class="n">i</span><span class="o">++;</span>
  <span class="n">n</span> <span class="o">=</span> <span class="n">n</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="o">;</span>
 <span class="o">}</span>

 <span class="k">return</span> <span class="o">-</span><span class="mi">1</span><span class="o">;</span>




}



/*
 * Checks index of last seq. of 2 consecutive 1. i.e: "1011001 -> index 3"
 * if no seq. found return -1
 *
 * @param n
 * @return
 /
public static int getLastIndexSeqOnes(int n) {
    // current and previous bit if set to 1 then true
    boolean cur, prev = false;



<span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
<span class="kt">int</span> <span class="n">highest</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span><span class="o">;</span>

<span class="k">while</span><span class="o">(</span><span class="n">n</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="o">)</span> <span class="o">{</span>
  <span class="k">if</span> <span class="o">(</span> <span class="o">(</span><span class="n">n</span> <span class="o">&amp;</span> <span class="mi">1</span><span class="o">)</span> <span class="o">==</span> <span class="mi">1</span><span class="o">)</span> <span class="o">{</span>
    <span class="n">cur</span> <span class="o">=</span> <span class="kc">true</span><span class="o">;</span>
  <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
    <span class="n">cur</span> <span class="o">=</span> <span class="kc">false</span><span class="o">;</span>
  <span class="o">}</span>
  <span class="k">if</span> <span class="o">(</span><span class="n">cur</span> <span class="o">&amp;&amp;</span> <span class="n">prev</span><span class="o">)</span> <span class="o">{</span>
      <span class="n">highest</span> <span class="o">=</span> <span class="n">i</span><span class="o">;</span>
  <span class="o">}</span>
  <span class="n">prev</span> <span class="o">=</span> <span class="n">cur</span><span class="o">;</span>

  <span class="n">i</span><span class="o">++;</span>
  <span class="n">n</span> <span class="o">=</span> <span class="n">n</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="o">;</span>
 <span class="o">}</span>

 <span class="k">return</span> <span class="n">highest</span><span class="o">;</span>




}



/*
 * Checks if number is sparse: if 2 consecutive 1 are present.
 * @param n
 * @return
 /
public static boolean isSparseBinaryNumber(int n) {
    // current and previous bit if set to 1 then true
    boolean cur, prev = false;



<span class="k">while</span><span class="o">(</span><span class="n">n</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="o">)</span> <span class="o">{</span>
  <span class="k">if</span> <span class="o">(</span> <span class="o">(</span><span class="n">n</span> <span class="o">&amp;</span> <span class="mi">1</span><span class="o">)</span> <span class="o">==</span> <span class="mi">1</span><span class="o">)</span> <span class="o">{</span>
    <span class="n">cur</span> <span class="o">=</span> <span class="kc">true</span><span class="o">;</span>
  <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
    <span class="n">cur</span> <span class="o">=</span> <span class="kc">false</span><span class="o">;</span>
  <span class="o">}</span>
  <span class="k">if</span> <span class="o">(</span><span class="n">cur</span> <span class="o">&amp;&amp;</span> <span class="n">prev</span><span class="o">)</span> <span class="o">{</span>
      <span class="k">return</span> <span class="kc">false</span><span class="o">;</span>
  <span class="o">}</span>
  <span class="n">prev</span> <span class="o">=</span> <span class="n">cur</span><span class="o">;</span>

  <span class="n">n</span> <span class="o">=</span> <span class="n">n</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="o">;</span>
 <span class="o">}</span>

 <span class="k">return</span> <span class="kc">true</span><span class="o">;</span>




}



public static int getLengthBits(int n) {
    int count = 0;
    while (n > 0) {
        count++;
        n = n >> 1;
    }
    return count;
}



public static String convertToBinaryString(int n) {
    StringBuilder sb = new StringBuilder();



 <span class="k">while</span><span class="o">(</span><span class="n">n</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="o">)</span> <span class="o">{</span>
  <span class="k">if</span> <span class="o">(</span> <span class="o">(</span><span class="n">n</span> <span class="o">&amp;</span> <span class="mi">1</span><span class="o">)</span> <span class="o">==</span> <span class="mi">1</span><span class="o">)</span> <span class="o">{</span>
   <span class="n">sb</span><span class="o">.</span><span class="na">append</span><span class="o">(</span><span class="s">"1"</span><span class="o">);</span>
  <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
   <span class="n">sb</span><span class="o">.</span><span class="na">append</span><span class="o">(</span><span class="s">"0"</span><span class="o">);</span>
  <span class="o">}</span>

  <span class="n">n</span> <span class="o">=</span> <span class="n">n</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="o">;</span>
 <span class="o">}</span>

 <span class="k">return</span> <span class="n">sb</span><span class="o">.</span><span class="na">reverse</span><span class="o">().</span><span class="na">toString</span><span class="o">();</span>




}



public static boolean getBit(int n, int index) {
    return ((n & (1 << index)) > 0);
}



public static int setBit(int n, int index, boolean b) {
    if (b) {
        return n | (1 << index);
    } else {
        return n & ~(1 << index);
    }
}



}

Full source code

comments powered by Disqus