Article directory
- Convert to Base -2 negative binary conversion
-
- Problem Description:
- analyze
- the code
-
Convert to Base -2 negative binary conversion
Description of problem:
Given an integer n, return the negative binary (base -2) representation of that integer as a binary string.
Note that the returned string cannot contain leading zeros unless the string is exactly “0”.
Simply put, it converts a decimal n into a negative binary string.
n range [0,10^9]
Analysis
For decimal n,
no
=
x
1
x
(
10
)
0
+
x
2
x
(
10
)
1
+
x
3
x
(
10
)
2
+
?
+
x
i
x
(
10
)
i
?
1
n = x_1\times(10)^{0} + x_2\times(10)^{1} + x_3\times(10)^{2} + \dots + x_i\times(10)^ {i-1}
n=x1?×(10)0 + x2?×(10)1 + x3?×(10)2 + ? + xi?×(10)i?1 , and the range of each digit is 0~9, Its expression is that each bit is
x
i
x_i
xi?,
x
i
x_i
The range of xi? is [0,9].
For the same value, decimal and binary, or N-ary, are different representations, and the final value they represent is the same.
So to represent such a value in decimal n, then the binary of n is
no
=
x
1
x
(
2
)
0
+
x
2
x
(
2
)
1
+
x
3
x
(
2
)
2
+
?
+
x
i
x
(
2
)
i
?
1
n = x_1\times(2)^{0} + x_2\times(2)^{1} + x_3\times(2)^{2} + \dots + x_i\times(2)^ {i-1}
n=x1?×(2)0 + x2?×(2)1 + x3?×(2)2 + ? + xi?×(2)i?1 What changes is the bit weight.
Therefore, converting decimal to binary is to find the remainder. Because of the characteristics of 2, each bit of binary will only be 0, 1. The specific writing method can be Baidu.
The conversion of decimal to x-base is actually similar to binary, using c to represent the remainder of the lowest bit of x-base,
no
=
x
?
b
+
C
n = X*b + C
n=X?b + C. The range of c is [0,x).*
But the negative base requires special handling, the negative binary of n,
no
=
x
1
x
(
?
2
)
0
+
x
2
x
(
?
2
)
1
+
x
3
x
(
?
2
)
2
+
?
+
x
i
x
(
?
2
)
i
?
1
n = x_1\times(-2)^{0} + x_2\times(-2)^{1} + x_3\times(-2)^{2} + \dots + x_i\times( -2)^{i-1}
n=x1?×(?2)0 + x2?×(?2)1 + x3?×(?2)2 + ? + xi?×(?2)i?1,
no
=
(
?
2
)
?
b
+
c
n = (-2)*b + c
n=(?2)?b + c, b and c are both integers. For negative binary, the value range of each bit is (-2,0], which is -1,0. However, due to different programming languages The meaning is very different.
Mathematically modulo
x
m
o
d
Y
=
x
?
Y
x
?
x
/
Y
?
X \mod Y = X -Y\times\lfloor X/Y \rfloor
XmodY=X?Y×?X/Y?,
0
< x m o d the y < the y , the y >
0
0< x \mod y < y, y>0
0
0
>
x
m
o
d
the y
>
the y
,
the y
< 0 0> x \mod y > y, y<0 0>xmody>y,y<0
But in JAVA, % is generally used to handle modulo operations, but this operator is actually a remainder. For ordinary scenarios, the results of remainder and modulus are the same, but similar to this problem, y<0,% The result of the calculation is -1,0,1.
So special handling is required.
However, -1 is not used in the actual representation, but a combination of the high bit + 1 and the current bit is 1.
if
c
=
?
1
,
no
=
(
?
2
)
?
b
+
(
?
1
)
=
>
no
=
(
?
2
)
?
(
b
+
1
)
+
1
c=-1, n = (-2)*b + (-1) => n = (-2)*(b + 1) + 1
c=?1,n=(?2)?b + (?1)=>n=(?2)?(b + 1) + 1, this processing is the difference of negative X base.
Code
public String baseNeg2(int n) {<!-- -->
if (n == 0) {<!-- -->
return "0";
}
int base = -2;
StringBuilder sb = new StringBuilder();
while(n!=0){<!-- -->
int r = n?se;
String s = r==0?"0":"1";
if(r!=0){<!-- -->
n-=1;
}
sb.append(s);
n/=-2;
}
int p = sb. length()-1;
while(p>0 & amp; & amp; sb.charAt(p)=='0') sb.deleteCharAt(p--);
sb. reverse();
return sb.toString();
}
Time complexity O(N) Space complexity: O(1)
tag
Array Math