5

Given an integer , print the next smallest and next largest number that have the same number of 1 bits in their binary representation

After Counting the number of 1's in the number.How to determine the next smallest number?

garima
  • 5,154
  • 11
  • 46
  • 77
  • 4
    So, is this homework? (I only ask since this is the second question of this type you've asked) – flight Mar 31 '11 at 10:06
  • 2
    no... go ahead to answer it..;) – garima Mar 31 '11 at 10:13
  • let say we have n = 0x11001101, x is next smallest. that means x is greater than n && x is the smallest among all greater && x has the same number of 1 bits as x does. Here is my rule to change from n to x: change the last 0 to 1; if it has 1 bits in the right, change the one most close to the last 0 to 0; otherwise, change the first 0 to 1, change the first 0's most close 1 to 0. I can see recursive way here. but still not clear about the fundamental law or theory. – SecureFish Jul 28 '11 at 22:23

4 Answers4

7

for next high you can use Hakmem 175 :

ITEM 175 (Gosper):

To get the next higher number with the same number of 1 bits:

unsigned nexthi_same_count_ones(unsigned a) {
   /* works for any word length */
 unsigned c = (a & -a);
 unsigned r = a+c;
  return (((r ^ a) >> 2) / c) | r;
}

For next lower I do not know a fast algorithm so I would use the classic approach, if the number is > then 2^0+2^1+...2^n then deduct one from your number and count the number of bits. The first number with n bits is the one.

Evg
  • 25,259
  • 5
  • 41
  • 83
Dumitrescu Bogdan
  • 7,127
  • 2
  • 23
  • 31
  • 3
    oops ... `nexthi_same_count_ones(0)` – pmg Mar 31 '11 at 10:51
  • 2
    Can you please explain it a little more about the algorithm? for example, what does each calculation mean – SecureFish Jul 28 '11 at 22:02
  • @Dumitrescu : I have a doubt, Most of the scenarios (specially in C) If we perform & operation on a number with its contemprary( - applied on that number). It will always render 1. Can we directly divide ((r^a) >> 2) by 1. Why do I need to compute that operation? Its just my doubt. Sorry if I dont understand something. – Rengasami Ramanujam Sep 22 '13 at 15:52
  • 2
    Bad variable naming and no explanation. You've made it way too hard to understand what is happening here. – Menezes Sousa Aug 24 '15 at 02:08
  • Well it's not my code, and the names are not mine. This is a "bit hack" for which I gave the source. Hackmem 175. It's take it or leave it. – Dumitrescu Bogdan Aug 24 '15 at 06:21
7

For the smaller

int getNextSmaller(int num) {
    return ~getNextLarger(~num);
}

Sometimes, things is just that simple. :)

http://www.sureinterview.com/shwqst/40004

SureInterview
  • 131
  • 1
  • 1
7

Here is a very good explanation. :)

Arihant Nahata
  • 1,802
  • 2
  • 19
  • 30
  • 1
    If you could, try and summarize the explanation in your answer. Links break, and then your answer becomes useless. – kamoroso94 Sep 09 '18 at 18:23
1

See for the sample number 156 below. I have also posted the source for detailed explanation.

{

x = 156
10011100 becomes 10100011  
To get the next higher number we need to set the 6th bit from LSB and shift
the string of 1's (3rd,4th,5th) to LSB positions 1,2 and drop 5th bit

so we get 163 - 10100011, which is next highest number with same number of 1's as 156.

00011100 - right most string of 1's in x
00000011 - right shifted pattern except left most bit ------> [A]
00010000 - isolated left most bit of right most 1's pattern
00100000 - shiftleft-ed the isolated bit by one position ------> [B]
10000000 - left part of x, excluding right most 1's pattern ------> [C]
10100000 - add B and C (OR operation) ------> [D]
10100011 - add A and D which is required number 163

}

{

uint_t snoob(uint_t x)
{
    uint_t rightOne;
    uint_t nextHigherOneBit;
    uint_t rightOnesPattern;
    uint_t next = 0;

    if(x){
        // right most set bit
        rightOne = x & -(signed)x;
        // reset the pattern and set next higher bit
        // left part of x will be here
        nextHigherOneBit = x + rightOne;
        // nextHigherOneBit is now part [D] of the above explanation.
        // isolate the pattern
        rightOnesPattern = x ^ nextHigherOneBit;
        // right adjust pattern
        rightOnesPattern = (rightOnesPattern)/rightOne;
        // correction factor
        rightOnesPattern >>= 2;
        // rightOnesPattern is now part [A] of the above explanation.
        // integrate new pattern (Add [D] and [A])
        next = nextHigherOneBit | rightOnesPattern;
    }
    return next;
}

}

source: http://www.geeksforgeeks.org/next-higher-number-with-same-number-of-set-bits/

john x
  • 21
  • 5