计算下一个更高的数字，它具有相同的置位位数？ [英] Calculating the next higher number which has same number of set bits?

问题描述

通过 geeksforgeeks 网站。

我想知道是否存在更好，更简单的解决方案？这有点复杂。只需一个算法就可以了。

解决方案

我很确定，该算法与链接算法一样高效且易于理解。

此处的策略是理解在不增加数字1的情况下增大数字的唯一方法是携带1，但是如果携带多个1，则必须将它们重新添加。 / p>

• 给出一个数字 1001 1100




• 将其右移，直到其值为奇数为止， 0010 0111 。记住移位数： shifts = 2;




• 将其右移，直到该值是偶数， 0000 0100 。记住执行的移位数和消耗的位。 班次+ = 3; bits = 3;




• 到目前为止，我们从算法中取了5个移位和3个位来携带可能的最低位数。现在我们将其还清。




• 使最右边的位为1。 0000 0101 。我们现在欠它2位。 位-= 1




• 左移3次以加0。 0010 1000 。我们这样做了三遍，因为 shifts-bits == 3 shifts-= 3




• 现在，我们欠数两位数和两次移位。因此将其左移两次，每次将最左边的位设置为1。 1010 0011 。我们已经偿还了所有零用钱和所有班次。 位-= 2;移动-= 2;位== 0; shifts == 0

这里还有其他一些示例...每个步骤都已显示如 current_val，shifts_owed，bits_owed

  0000 0110 
 0000 0110，0，0＃开始
 0000 0011，1，0＃右移直到奇数
 0000 0000，3，2＃右移直到偶
 0000 0001，3，1＃设置LSB 
 0000 0100，1，1＃左移0的
 0000 1001，0，0＃左移1的
  

---

  0011 0011 
 0011 0011，0，0＃起始
 0011 0011，0， 0＃右移至奇数
 0000 1100，2，2＃右移至偶数
 0000 1101，2，1＃设置LSB 
 0001 1010，1，1＃左移0的
 0011 0101，0，0＃向左移1的
  

---

A solution is given to this question on geeksforgeeks website.

I wish to know does there exist a better and a simpler solution? This is a bit complicated to understand. Just an algorithm will be fine.

解决方案

I am pretty sure this algorithm is as efficient and easier to understand than your linked algorithm.

The strategy here is to understand that the only way to make a number bigger without increasing its number of 1's is to carry a 1, but if you carry multiple 1's then you must add them back in.

• Given a number 1001 1100

• Right shift it until the value is odd, 0010 0111. Remember the number of shifts: shifts = 2;

• Right shift it until the value is even, 0000 0100. Remember the number of shifts performed and bits consumed. shifts += 3; bits = 3;

• So far, we have taken 5 shifts and 3 bits from the algorithm to carry the lowest digit possible. Now we pay it back.

• Make the rightmost bit 1. 0000 0101. We now owe it 2 bits. bits -= 1

• Shift left 3 times to add the 0's. 0010 1000. We do it three times because shifts - bits == 3 shifts -= 3

• Now we owe the number two bits and two shifts. So shift it left twice, setting the leftmost bit to 1 each time. 1010 0011. We've paid back all the bits and all the shifts. bits -= 2; shifts -= 2; bits == 0; shifts == 0

Here's a few other examples... each step is shown as current_val, shifts_owed, bits_owed

0000 0110
0000 0110, 0, 0 # Start
0000 0011, 1, 0 # Shift right till odd
0000 0000, 3, 2 # Shift right till even
0000 0001, 3, 1 # Set LSB
0000 0100, 1, 1 # Shift left 0's
0000 1001, 0, 0 # Shift left 1's

---

0011 0011
0011 0011, 0, 0 # Start
0011 0011, 0, 0 # Shift right till odd
0000 1100, 2, 2 # Shift right till even
0000 1101, 2, 1 # Set LSB
0001 1010, 1, 1 # Shift left 0's
0011 0101, 0, 0 # Shift left 1's

---

这篇关于计算下一个更高的数字，它具有相同的置位位数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！