不使用算术运算符减 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，使用了按位运算符。

我希望这篇文章能帮助您了解问题的方方面面。