找到最小的二进制数字，其中没有连续的1。

huangapple
go评论160阅读模式
英文:

Find the smallest binary number without continous 1

问题

这里是代码部分的翻译：

  1. String a = "11001110101010";
  2. String b = "";
  3. int d = 0;
  4. for(int i = a.length()-1; i>0;i--){
  5.     if(a.charAt(i) == '1' && a.charAt(i-1)=='1'){
  6.         while(a.charAt(i)=='1'){
  7.             b = b + '0';
  8.             if(i!=0){i--;}
  9.             d++;
  10.         }
  11.     }
  12.     b = b + a.charAt(i);
  13. }
  14. StringBuffer c = new StringBuffer(b);
  15. System.out.println(c.reverse());

希望这能对你有所帮助。如果你有其他问题，请随时提出。

英文:

So here is the thing.
I have to write code to show a binary number X's next smallest "code-X number" which is bigger than binary number X.
code-X number is a binary number which have no continuously 1. For example: 1100 is not a code X number because it has 11, and 1001001001 is a code-X number
Here is my code

  1. String a = "11001110101010";
  2.     String b = "";
  3.     int d = 0;
  4.     for(int i = a.length()-1; i>0;i--){
  5.         if(a.charAt(i) == '1' && a.charAt(i-1)=='1'){
  6.         while(a.charAt(i)=='1'){
  7.             b = b + '0';
  8.             if(i!=0){i--;}
  9.             d++;
  10.         }
  11.         }
  12.         b = b + a.charAt(i);
  13.     }
  14.     StringBuffer c = new StringBuffer(b);
  15.     System.out.println(c.reverse());

I plan on copy the binary string to string b, replace every '1' which next i is '1' into '0' and insert an '1'
like:
1100 ---> 10000
but i have no idea how to do it 找到最小的二进制数字，其中没有连续的1。
May you help me some how? Thanks

答案1

得分: 3

以下是代码的中文翻译：

尝试这个。这个处理任意长度的位串。算法如下。

  • 需要有条件地修改最后两位，以强制更改，如果数字不是codeEx数字。这确保它将更高。感谢John Mitchell提出的观察。
  • 从左边开始，找到第一个1组。例如，0110
  • 如果不在开头，将其替换为100以获得1000
  • 否则，在开头插入1。
  • 在所有情况下，将分组右侧的所有内容替换为0。
  1. String x = "10000101000000000001000001000000001111000000000000110000000000011011";
  3. System.out.println(x.length());
  4. String result = codeX(x);
  6. System.out.println(x);
  7. System.out.println(result);
  9. public static String codeX(String bitStr) {
  10.     StringBuilder sb = new StringBuilder(bitStr);
  11.     int i = 0;
  13.     int len = sb.length();
  14.     // 进行调整以确保新数字大于原始数字。如果词以00或10结尾，那么添加一个1将在所有情况下增加值。
  15.     // 如果以01结尾，那么用10替换将产生相同的效果。一旦完成，算法就接管查找下一个CodeX数字。
  16.     if (s.equals("01")) {
  17.         sb.replace(len - 2, len, "10");
  18.     } else {
  19.         sb.replace(len - 1, len, "1");
  20.     }
  21.     while ((i = sb.indexOf("11")) >= 0) {
  22.         sb.replace(i, len, "0".repeat(len - i));
  23.         if (i != 0) {
  24.             sb.replace(i - 1, i + 2, "100");
  25.         } else {
  26.             sb.insert(i, "1");
  27.         }
  28.     }
  29.     String str = sb.toString();
  30.     i = str.indexOf("1");
  31.     return i >= 0 ? str.substring(i) : str;
  32. }

打印结果：

  1. 10000101000000000001000001000000001111000000000000110000000000011011
  2. 10000101000000000001000001000000010000000000000000000000000000000000
英文:

Try this. This handles arbitrary length bit strings. The algorithm is as follows.

  • Needed to conditionally modify last two bits to force a change if the number is not a codeEx number. This ensures it will be higher. Thanks to John Mitchell for this observation.
  • Starting from the left, find the first group of 1's. e.g 0110
  • If not at the beginning replace it with 100 to get 1000
  • Otherwise, insert 1 at the beginning.
  • In all cases, replace everything to the right of the grouping with 0's.
  1. String x = "10000101000000000001000001000000001111000000000000110000000000011011";
  3. System.out.println(x.length());
  4. String result = codeX(x);
  6. System.out.println(x);
  7. System.out.println(result);
  10. public static String codeX(String bitStr) {
  11. 	StringBuilder sb = new StringBuilder(bitStr);
  12. 	int i = 0;
  14.    
  15.     int len = sb.length();
  16. 	// Make adjust to ensure new number is larger than
  17. 	// original.  If the word ends in 00 or 10, then adding one will
  18. 	// increase the value in all cases.  If it ends in 01
  19. 	// then replacing with 10 will do the same.  Once done
  20. 	// the algorithm takes over to find the next CodeX number.
  21. 	if (s.equals("01")) {
  22. 		sb.replace(len - 2, len, "10");
  23. 	} else {
  24. 		sb.replace(len- 1, len, "1");
  25. 	}
  26. 	while ((i = sb.indexOf("11")) >= 0) {
  27. 		sb.replace(i, len, "0".repeat(len - i));
  28. 		if (i != 0) {
  29. 			sb.replace(i - 1, i + 2, "100");
  30. 		} else {
  31. 			sb.insert(i, "1");
  32. 		}
  33. 	}
  34. 	String str = sb.toString();
  35. 	i = str.indexOf("1");
  36. 	return i >= 0 ? str.substring(i) : str;
  37. }

Prints

  1. 10000101000000000001000001000000001111000000000000110000000000011011
  2. 10000101000000000001000001000000010000000000000000000000000000000000
  6. </details>
  10. # 答案2
  11. **得分**: 2
  13. Using raw binary you can use the following.
  15. ```java
  16. public static void main(String[] args) {
  17.     long l = 0b1000010100000000010000010000000011110000000000110000000000011011L;
  18.     System.out.println(
  19.             Long.toBinaryString(nextX(l)));
  20. }
  22. public static long nextX(long l) {
  23.     long l2 = l >>> 1;
  24.     long next = Long.highestOneBit(l & l2);
  25.     long cutoff = next << 1;
  26.     long mask = ~(cutoff - 1);
  27.     return (l & mask) | cutoff;
  28. }

prints

  1. 1000010100000000010000010000000010000000000000000000000000000000

EDIT: Based on @WJS correct way to find the smallest value just larger.

英文:

Using raw binary you can use the following.

  1. public static void main(String[] args) {
  2.     long l = 0b1000010100000000010000010000000011110000000000110000000000011011L;
  3.     System.out.println(
  4.             Long.toBinaryString(nextX(l)));
  5. }
  7. public static long nextX(long l) {
  8.     long l2 = l &gt;&gt;&gt; 1;
  9.     long next = Long.highestOneBit(l &amp; l2);
  10.     long cutoff = next &lt;&lt; 1;
  11.     long mask = ~(cutoff - 1);
  12.     return (l &amp; mask) | cutoff;
  13. }

prints

  1. 1000010100000000010000010000000010000000000000000000000000000000

EDIT: Based on @WJS correct way to find the smallest value just larger.

答案3

得分: 0

这是WJS的99%正确答案的一个小扩展。

只有一件事缺失，如果原始的X字符串中没有连续的1，数字不会递增。主方法的这个修改处理了这个问题。

编辑；添加了一个else{}。从字符串的末尾开始，直到找到一个0之前，所有数字都应该被反转。然后我们将其更改为1，并在将结果字符串传递给WJS的codeX函数之前中断。
（codeX版本不包括sb.replace(len-2,len，"11");）

  1. public static void main(String[] args) {
  2.     String x = "10100";
  3.     StringBuilder sb = new StringBuilder(x);
  5.     if (!x.contains("11")) {
  6.         for (int i = sb.length()-1; i >= 0; i--) {
  7.             if (sb.charAt(i) == '0') {
  8.                 sb.setCharAt(i, '1');
  9.                 break;
  10.             } else {
  11.                 sb.setCharAt(i, '0');
  12.             }
  13.         }
  14.     }
  16.     String result = codeX(sb.toString());
  18.     System.out.println(x);
  19.     System.out.println(result);
  20. }
英文:

This is a slight expansion WJS' 99% correct answer.

There is just one thing missing, the number is not incremented if there are no consecutive 1's in the original X string.
This modification to the main method handles that.

Edit; Added an else {}. Starting from the end of the string, all digits should be inverted until a 0 is found. Then we change it to a 1 and break before passing the resulting string to WJS' codeX function.
(codeX version does not include sb.replace(len-2,len,"11");)

  1. public static void main(String[] args) {
  2.     String x = &quot;10100&quot;;
  3.     StringBuilder sb = new StringBuilder(x);
  5.     if (!x.contains(&quot;11&quot;)) {
  6.         for (int i = sb.length()-1; i &gt;= 0; i--) {
  7.             if (sb.charAt(i) == &#39;0&#39;) {
  8.                 sb.setCharAt(i, &#39;1&#39;);
  9.                 break;
  10.             } else {
  11.                 sb.setCharAt(i, &#39;0&#39;);
  12.             }
  13.         }
  14.     }
  16.     String result = codeX(sb.toString());
  18.     System.out.println(x);
  19.     System.out.println(result);
  20. }

huangapple
  • 本文由 发表于 2020年8月12日 00:00:15
  • 转载请务必保留本文链接：https://go.coder-hub.com/63361988.html
  • java
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定