負二進制表示法-“奮斗杯”編程大賽題目
- 0、題目
- 1、思考
- 1.1 先試一個簡單的值 16
- 1.2 再試一下題干中的值3
- 1.3 試一下特殊值-13
- 2 代碼實作go和java
0、題目
計算機里的數都是二進制表示，其實還有一種負二進制表示法，都不需要符號位，
如 3 的負二進制表示法為 111，因為 (-2)2 + (-2)1 + (-2)0 = 4-2+1 = 3 ，
再如 -3 的負二進制表示法為 1101，因為 (-2)3 + (-2)2 + (-2)0 = -8+4+1 = -3 ，
要求輸入一個整數，輸出其負二進制表示，
- Golang
- Java
1、思考
| 指數 | 冪 | 值 |
|---|---|---|
| 0 | (-2)0 | 1 |
| 1 | (-2)1 | -2 |
| 2 | (-2)2 | 4 |
| 3 | (-2)3 | -8 |
| 4 | (-2)4 | 16 |
| 5 | (-2)5 | -32 |
由表可知，負二進制理論上可以表示計算機位數范圍內的任意整數值，
準備幾個特殊的值備用，(0)10 = (0)-2 , (1)10 = (1)-2 , (-1)10 = (11)-2
首先回憶一下十進制轉二進制的方法，除2取余倒著寫，嗯，我們先試一下，看看能不能也用到負二進制的換算上，
1.1 先試一個簡單的值 16
- 16/(-2) = -8 ······ 0
- -8/(-2) = 4 ······ 0
- 4/(-2) = -2 ······ 0
- -2/(-2) = 1 ······ 0
所以 (16)10 = (10000)-2 ，嗯，看起來好像沒毛病，
1.2 再試一下題干中的值3
- 3/(-2) = -1 ······ 1
- -1/(-2) = 0 ······ -1
呃，好像哪里不對，雖然根據之前的特殊值 (-1)10 = (11)-2 ，可以推出 3/(-2) 商為 -1 余數為 1，所以 (3)10 = (111)-2，貌似也搞定了，
1.3 試一下特殊值-13
先在代碼里運行一下 -13/(-2)，得到商為6，余數為-1，等等，余數為-1是什么鬼，余數不應該是1或者0嗎？再想想，應該得到的商為7，余數為1，這樣就行了，于是：
- -13/(-2) = 7 ······ 1
- 7/(-2) = -3 ······ 1
- -3/(-2) = 2 ······ 1
- 2/(-2) = -1 ······ 0
- -1/(-2) = 1 ······ 1
所以，(-13)10 = (110111)-2 ，
驗算一下，(-2)5+(-2)4+(-2)2+(-2)1+(-2)0 = -32+16+4-2+1 = -13 ，沒毛病！
結論，當被除數為負數，余數為-1時，計算所得的商應該加一，余數就變為正1，
2 代碼實作go和java
//go語言實作
func intToNegativeBinary(n int) {
if n == 0 {
fmt.Println(0)
return
}
const BASE = -2
var ans []byte
for n != 1 {
if n > 0 {
ans = append(ans, byte('0'+n%BASE))
n /= BASE
} else {
yu := n % BASE
if yu == -1 {
//余數為-1
n = n/BASE + 1
ans = append(ans, '0'+byte(1))
} else {
ans = append(ans, '0'+byte(yu))
n /= BASE
}
}
}
//把最后剩下的1加進去
ans = append(ans, '0'+byte(1))
length := len(ans)
//反轉
for i := 0; i < length/2; i++ {
ans[i], ans[length-1-i] = ans[length-1-i], ans[i]
}
fmt.Println(string(ans))
}
//java代碼實作
public static void intToNegativeBinary(int n){
if (n == 0){
System.out.println(0);
return;
}
int BASE = -2;
StringBuilder str = new StringBuilder();
while (n != 1){
if (n > 0){
str.append(n%BASE);
n/=BASE;
} else {
int yu = n%BASE;
if (yu == -1){
//余數為-1
n = n/BASE + 1;
str.append(1);
} else {
str.append(n%BASE);
n/=BASE;
}
}
}
//把最后剩下的1加進去
str.append(1);
str.reverse();
System.out.println(str);
}
java代碼，也可以不用先append，再reverse，可以直接用 str.insert(0, 1); 實作向最前append，
自己測驗了一下，大量資料時，如量級在105，兩個時差接近20倍，所以先append再reverse 速度更快，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/200461.html
標籤：其他