不使用算術運算子減 1

---

這個問題要求我們不使用算術運算子來減 1。在問題中，我們將得到任何整數 N 作為輸入，我們需要從該數字中減去 1，或者簡單地說，我們需要列印 N-1。我們的任務是在不使用任何算術運算子的情況下執行此操作。

算術運算包括對數字進行各種運算，例如加法(+)、減法(-)、乘法(*)、除法(/)、取模(%) 等。這些運算在每種程式語言中都支援數字運算。儘管如此，我們仍需要從數字中減去 1。

例如，

輸入

7

輸出

6

說明：輸入的數字 N 為 7。從 N 中減去 1 得到 6，這是期望的結果。請記住，我們不允許對 N 執行任何數學運算。

輸入

24

輸出

23

說明：從數字 N 中減去 1。

讓我們看看我們可以使用什麼演算法來解決問題，而無需使用任何算術運算子。

演算法

可以使用位操作技術來解決此問題，而無需使用算術運算子，這些技術利用了 C++ 的按位運算子。按位運算包括 AND 運算子 (&)、OR 運算子 (|)、XOR 運算子 (^)、NOT 運算子 (~)、左移運算子 (<<) 和右移運算子 (>>)。在 C 中可以執行。為了在 C++ 中處理位，我們使用一些基本的按位運算。

為了解決這個問題，此方法僅使用 XOR 運算子和左移運算子。

因為任何數字都可以用二進位制形式表示。10 的二進位制表示為 1010。

如果我們觀察每個形如 $\mathrm{2^{n}}$ 的數字，其中 n 可以是任何正整數，可以表示為

$\mathrm{2^n\:=\:2^{n-1}+2^{n-2}+.....+2^{0}+1}$

如果數字是，從 0 到 n-1 開始的所有 2 的冪之和將給出等於 (number-1) 的數字。

我們已經知道，任何以二進位制形式表示的數字都遵循從 $\mathrm{2^{0}}$ 到 $\mathrm{2^{31}}$ 的相同模式，在 32 位整數中。

因此，如果我們想從任何數字中減去 1，只需找到第一個 1 位，並將之後的 0 位全部轉換為 1，並將該 1 位轉換為 0，保持其餘位不變，將給出等於 N-1 的數字。

讓我們在我們的方法中檢視此演算法的實現。

方法

• 我們將建立一個變數 'a' 來查詢數字的第一個 1 位。

• 為了找到數字的第一個 1 位，請繼續在 while 迴圈中迭代，直到 (N&a)=0。(N&a) 僅當兩個位都為 1 時才返回 1。

• 在迴圈中迭代時，使用 XOR 運算子不斷更新數字 N 的位，直到我們找到數字的第一個 1 位。

• 除了更新數字 N 的位之外，每次都將 a 左移以檢查第一個 1 位。

• 一旦我們找到第一個 1 位，迴圈將中斷。到目前為止，我們已經使用 1 更新了第一個 1 位之後的所以位。

• 現在使用 XOR 運算子，我們將使用 0 更新數字的第一個 1 位，因為當輸入相同的時候 XOR 返回 0。

• 然後返回數字 N，它現在將等於 N-1。

以下是此方法的 C++ 程式碼實現

示例

#include <bits/stdc++.h>

using namespace std;

//function to subtract 1 using bitwise operators
int subtract(int N){
   int a=1; //to find the first 1 bit of the number N
   
   while((N&a)==0){  //iterate in the loop until we find the first 1 bit as 0&1=0 and 1&1=1
      
    N=N^a; //keep updating the bits with 1 which are after first 1 bit of the number N
      
      a=a<<1; //left shift a by 1
   }
   N=N^a; //update the first 1 bit of the number with 0 as 1^1=0
   
   return N; //return the number which is equal to N-1
}

int main()
{
   int N=175;
   
   cout<<subtract(N)<<endl;
   
   N=56;
   cout<<subtract(N)<<endl;

   return 0;
}

輸出

174
55

時間複雜度：O(log x)，x 等於給定數字 N 中的位數。

空間複雜度：O(1)，因為我們不使用任何額外的空間。

結論

本文透過一種有效的方法解決了不使用任何算術運算子（即 C++ 中的 +、-、/、%、*）從給定數字 N 中減去 1 的問題，該方法利用了位操作的方法。為了從給定的整數中減去 1，使用了按位運算子。

我希望這篇文章能幫助您瞭解問題的方方面面。