问题描述
通过网站。
我想知道是否存在更好,更简单的解决方案?这有点复杂。只需一个算法就可以了。
我很确定,该算法与链接算法一样高效且易于理解。
此处的策略是理解在不增加数字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 becauseshifts - 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
这篇关于计算下一个更高的数字,它具有相同的置位位数?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!