Java利用位運算實現加減乘除的方法詳解

2022-08-29 22:05:44

前言

我們經常使用的加減乘除，我們所看到的只是表面的效果，那麼加減乘除在底層究竟是怎麼實現的？今天就讓我們一探究竟.今天用位運算實現的加減乘除不使用任何的加減乘除符號.

一、常見位運算

1. &運算

&運算二進位制每一位全1為1，否則為0

public static void main(String[] args) {
        int a = 1;
        int b = 3;
        System.out.println(a & b);
    }

2. |運算

|運算二進位制每一位有1為1，全0為0

public static void main(String[] args) {
        int a = 1;
        int b = 3;
        System.out.println(a | b);
    }

3. ^運算

^運算二進位制每一位不同為1，相同為0

public static void main(String[] args) {
        int a = 1;
        int b = 3;
        System.out.println(a ^ b);
    }

4. ~運算

~運算是二進位制每一位按位元取反.

public static void main(String[] args) {
        int a = 1;
        System.out.println(~a);
    }

二、位運算實現加法

public static void main(String[] args) {
        int a = 1;
        int b = 3;
        System.out.println(a + b);
    }

下來我們用位運算實現一下加法.

我們進行一次互斥或運算就相當於進行一次無進位加法，那這樣也不能實現加法，那我們得想辦法，實現進位的數值.

進行一次與運算，只有同時為1才為1，也當同時為1時，我們需要進位，所以我們進行與運算後進行左移一位的操作，即可得到進位後的數值.

我們對互斥或運算和與運算後左移一位的結果進行相加即可，但我們只能進行位運算，所以我們只能再次進行互斥或運算與與運算，直到雲運算的結果為0時，我們的互斥或運算的結果即為加法的結果.

public static int bitAdd(int a,int b) {
        int sum = 0;
        while(b != 0) {
            sum = a ^ b;
            b = (a & b) << 1;
            a = sum;
        }
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(bitAdd(1,2));
    }

三、位運算實現減法

public static void main(String[] args) {
        int a = 1;
        int b = 3;
        System.out.println(a - b);
    }

下來我們用位運算實現一下減法.

在我們有了位運算實現加法的基礎之後，我們的減法就變得簡單了，a - b == a + ( -b ),所以我們只需要將b變為-b即可實現減法功能，但我們不能使用負號，那我們來用位運算來實現一下.

public static void main(String[] args) {
        System.out.println(~3);
    }

我們可以發現一個數取反與相反數差一，我們取反加一即可得到相反數.

public static void main(String[] args) {
        System.out.println(~3 + 1);
    }

public static int bitAdd(int a,int b) {
        int sum = 0;
        while(b != 0) {
            sum = a ^ b;
            b = (a & b) << 1;
            a = sum;
        }
        return sum;
    }

    public static int bitSub(int a,int b) {
        return bitAdd(a,~b+1);
    }

    public static void main(String[] args) {
        System.out.println(bitSub(1,3));
    }

四、位運算實現乘法

public static void main(String[] args) {
        int a = 1;
        int b = 3;
        System.out.println(a * b);
    }

我們小學的時候是怎麼進行乘法的，按位元相乘，每一位和每一位相乘.

二進位制中也是一樣的，按位元相乘，如果被乘數二進位制位是1則與乘數相乘.每次運算進行移位

public static int bitAdd(int a,int b) {
        int sum = 0;
        while(b != 0) {
            sum = a ^ b;
            b = (a & b) << 1;
            a = sum;
        }
        return sum;
    }
    public static int bitMul(int a,int b) {
        int sum = 0;
        while(b != 0) {
            if((b & 1) != 0) {
                sum += a;
            }
            a <<= 1;
            b >>>= 1;
        }
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(bitMul(1,3));
    }

五、位運算實現除法

public static void main(String[] args) {
        int a = 7;
        int b = 2;
        System.out.println(a / b);
    }

我們在用位運算實現除法時，採用逆推的方式，a / b = c,

a = c * b。

我們只需要求出a減去b向左的移位，只要滿足a <= b的移位即可，每次移動多少位即a / b的結果二進位制中某一位為1，以此迴圈倒推即可.

public static int bitAdd(int a,int b) {
        int sum = 0;
        while(b != 0) {
            sum = a ^ b;
            b = (a & b) << 1;
            a = sum;
        }
        return sum;
    }
    public static int negNum(int n) {
        //轉化為相反數
        return bitAdd(~n,1);
    }
    public static int minus(int a,int b) {
        //實現兩個數相減
        return bitAdd(a,negNum(b));
    }
    public static boolean isNeg(int n) {
        //判斷是否為負數
        return n < 0;
    }
    public static int bitDiv(int a,int b) {
        int x = isNeg(a) ? negNum(a) : a;
        int y = isNeg(b) ? negNum(b) : b;
        int res = 0;
        for (int i = 30; i >= 0 ; i = minus(i,1)) {
            if((x >> i) >= y) {
                res |= (1 << i);
                x = minus(x,y << i);
            }
        }
        return isNeg(a) != isNeg(b) ? negNum(res) : res;

    }

    public static void main(String[] args) {
        int a = 7;
        int b = 2;
        System.out.println(bitDiv(a,b));
    }