给定一个数字x，在其二进制表示中找到下一个具有相同1位数的数字。 例如，考虑x＝12，其二进制表示为1100（不包括32位机器上的前导零点）。它包含两个逻辑1位。具有两个逻辑1位的下一个更高的数字是17（10001 2. ). 算法： 当我们观察从0到2的二进制序列时 N –1（n是位的#），最右边的位（最低有效位）比最左边的位变化快。其思想是找到x中最右边的1字符串，并将模式移到最右边，除了模式中最左边的位。将模式中最左边的位（省略的位）移动到x的左边一个位置。举个例子就更清楚了，
null
x = 156
10
x = 10011100
(2)
1001110000011100 - right most string of 1's in x00000011 - right shifted pattern except left most bit ------> [A]00010000 - isolated left most bit of right most 1's pattern00100000 - 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
(10) 在用很少的例子练习之后，它很容易理解。使用下面给定的程序生成更多集合。 程序设计： 我们需要注意一些关于二进制数的事实。表达式x&-x将隔离x中最右边的集合位（确保x将使用2的补码形式表示负数）。如果我们将结果添加到x中，x中最右边的1字符串将被重置，该1模式左边的立即数“0”将被设置，这是上述解释的[B]部分。例如，如果x=156，x&-x将产生00000100，将该结果与x相加将产生10100000（参见D部分）。我们用1的模式的右移部分向左移动（上面解释的A部分）。 实现A部分有不同的方法。右转本质上是一种分工操作。我们的除数应该是多少？显然，它应该是2的倍数（避免右移时出现0.5的错误），并且应该将最右边的1的模式移到最右边。表达式（x&-x）将用于除数。数字X和用于重置最右边位的表达式之间的EX-OR操作将隔离最右边1的模式。 修正系数： 请注意，我们正在向位模式添加最右边的设置位。加法操作会导致位位置发生移位。二元系统的重量是2，一次移位会使重量增加2倍。自从人数增加( 右翼燕鸥 在代码中，如果使用两次，错误会传播两次。这个错误需要纠正。右移2个位置将纠正结果。 这个程序的流行名称是 s 阿美 N 乌姆 o F o 氖 B 它的
C++
#include<iostream> using namespace std; typedef unsigned int uint_t; // this function returns next higher number with same number of set bits as x. 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; } int main() { int x = 156; cout<< "Next higher number with same number of set bits is " <<snoob(x); getchar (); return 0; } |
JAVA
// Java Implementation on above approach class GFG { // this function returns next higher // number with same number of set bits as x. static int snoob( int x) { int rightOne, nextHigherOneBit, rightOnesPattern, next = 0 ; if (x > 0 ) { // right most set bit rightOne = x & -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; } // Driver code public static void main (String[] args) { int x = 156 ; System.out.println( "Next higher number with same" + "number of set bits is " +snoob(x)); } } // This code is contributed by mits |
Python 3
# This function returns next # higher number with same # number of set bits as x. def snoob(x): next = 0 if (x): # right most set bit rightOne = x & - (x) # reset the pattern and # set next higher bit # left part of x will # be here nextHigherOneBit = x + int (rightOne) # nextHigherOneBit is # now part [D] of the # above explanation. # isolate the pattern rightOnesPattern = x ^ int (nextHigherOneBit) # right adjust pattern rightOnesPattern = ( int (rightOnesPattern) / int (rightOne)) # correction factor rightOnesPattern = int (rightOnesPattern) >> 2 # rightOnesPattern is now part # [A] of the above explanation. # integrate new pattern # (Add [D] and [A]) next = nextHigherOneBit | rightOnesPattern return next # Driver Code x = 156 print ( "Next higher number with " + "same number of set bits is" , snoob(x)) # This code is contributed by Smita |
C#
// C# Implementation on above approach using System; class GFG { // this function returns next higher // number with same number of set bits as x. static int snoob( int x) { int rightOne, nextHigherOneBit, rightOnesPattern, next = 0; if (x > 0) { // right most set bit rightOne = x & -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; } // Driver code static void Main() { int x = 156; Console.WriteLine( "Next higher number with same" + "number of set bits is " + snoob(x)); } } // This code is contributed by mits |
PHP
<?php // This function returns next higher number // with same number of set bits as x. function snoob( $x ) { $next = 0; if ( $x ) { // right most set bit $rightOne = $x & - $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 = intval (( $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 ; } // Driver Code $x = 156; echo "Next higher number with same " . "number of set bits is " . snoob( $x ); // This code is contributed by ita_c ?> |
Javascript
<script> // this function returns next higher // number with same number of set bits as x. function snoob(x) { let rightOne, nextHigherOneBit, rightOnesPattern, next = 0; if (x > 0) { // right most set bit rightOne = x & -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; } // Driver code let x = 156; document.write( "Next higher number with same " + "number of set bits is " +snoob(x)); // This code is contributed by avanitrachhadiya2155 </script> |
输出：
Next higher number with same number of set bits is 163
时间复杂性： O（1）
辅助空间： O（1）
用法： 查找/生成子集。 变化：
- 写一个程序，找到一个比给定值小的数字，逻辑1位的数字是多少？（非常简单）
- 如何计算或生成给定集合中可用的子集？
参考资料：
– 文基 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
