Problem

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

Examples

Example 1:

1
2
3

Input: number = 3
Output: 5
Explanation: Next higher number for 3 is 5. i.e. (00000011 => 00000101). Likewise next lower number of 5 is 3.

Solution

Method 1 - Adding or subtracting 1 until we have same number of 1s

For the next largest, keep adding 1 to the number until find the number that has same number of 1 bits. For the next smallest, keep decreasing 1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

public static int findNextSmallest(int number) {
	int result = number - 1;

	while (Integer.bitCount(result) != Integer.bitCount(number)) {
		result--;
	}

	return result;
}


public static int findNextLargest(int number) {
	int result = number + 1;

	while (Integer.bitCount(result) != Integer.bitCount(number)) {
		result++;
	}

	return result;
}

Method 2- Change the bits

For getting the next higher number

  • Traverse from right to left i.e. LSB to MSB. Once we’ve passed a 1, turn on the next 0. We’ve now increased the number by 2^i. Yikes! Example: xxxxx011100 becomes xxxxx111100.

  • Turn off the one that’s just to the right side of that. We’re now bigger by 2^i - 2^(i-1). Example: xxxxx111100 becomes xxxxx101100

  • Make the number as small as possible by rearranging all the 1s to be as far right as possible: Example: xxxxx101100 becomes xxxxx100011

For the next smaller number We can do something like this.

1
2
3

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

i.e. follow the above algorithm for number’s complement.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

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


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


public int GetNext_NP(int n) {
	if (n <= 0)
		return -1;
	int index = 0;
	int countOnes = 0;

	// Find first one.
	while (!GetBit(n, index))
		index++;

	// Turn on next zero.
	while (GetBit(n, index)) {
		index++;
		countOnes++;
	}

	n = SetBit(n, index, true);

	// Turn off previous one
	index--;
	n = SetBit(n, index, false);
	countOnes--;

	// Set zeros
	for (int i = index - 1; i >= countOnes; i--) {
		n = SetBit(n, i, false);
	}

	// Set ones
	for (int i = countOnes - 1; i >= 0; i--) {
		n = SetBit(n, i, true);
	}

	return n;
}


public int GetPrevious_NP(int n) {
	if (n <= 0)
		return -1; // Error
	int index = 0;
	int countZeros = 0;

	// Find first zero.
	while (GetBit(n, index))
		index++;

	// Turn off next 1.
	while (!GetBit(n, index)) {
		index++;
		countZeros++;
	}

	n = SetBit(n, index, false);

	// Turn on previous zero
	index--;
	n = SetBit(n, index, true);
	countZeros--;

	// Set ones
	for (int i = index - 1; i >= countZeros; i--) {
		n = SetBit(n, i, true);
	}

	// Set zeros
	for (int i = countZeros - 1; i >= 0; i--) {
		n = SetBit(n, i, false);
	}

	return n;
}

References