0、題目

計算機里的數都是二進制表示，其實還有一種負二進制表示法，都不需要符號位，

如 3 的負二進制表示法為 111，因為 (-2)² + (-2)¹ + (-2)⁰ = 4-2+1 = 3 ，

再如 -3 的負二進制表示法為 1101，因為 (-2)³ + (-2)² + (-2)⁰ = -8+4+1 = -3 ，

要求輸入一個整數，輸出其負二進制表示，

Golang
Java

1、思考

指數	冪	值
0	(-2)⁰	1
1	(-2)¹	-2
2	(-2)²	4
3	(-2)³	-8
4	(-2)⁴	16
5	(-2)⁵	-32

由表可知，負二進制理論上可以表示計算機位數范圍內的任意整數值，
準備幾個特殊的值備用，(0)₁₀ = (0)_-2 , (1)₁₀ = (1)_-2 , (-1)₁₀ = (11)_-2

首先回憶一下十進制轉二進制的方法，除2取余倒著寫，嗯，我們先試一下，看看能不能也用到負二進制的換算上，

1.1 先試一個簡單的值 16

16/(-2) = -8 ······ 0
-8/(-2) = 4 ······ 0
4/(-2) = -2 ······ 0
-2/(-2) = 1 ······ 0

所以 (16)₁₀ = (10000)_-2 ，嗯，看起來好像沒毛病，

1.2 再試一下題干中的值3

3/(-2) = -1 ······ 1
-1/(-2) = 0 ······ -1

呃，好像哪里不對，雖然根據之前的特殊值 (-1)₁₀ = (11)_-2 ，可以推出 3/(-2) 商為 -1 余數為 1，所以 (3)₁₀ = (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)₁₀ = (110111)_-2 ，
驗算一下，(-2)⁵+(-2)⁴+(-2)²+(-2)¹+(-2)⁰ = -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，
自己測驗了一下，大量資料時，如量級在10⁵，兩個時差接近20倍，所以先append再reverse 速度更快，

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/201425.html

標籤：其他

上一篇：OpenCV車牌定位(C++)

下一篇：【單片機學習】第六課：單片機控制第一個外設-LED燈