C++ 中的奇数数字

在本文中，我们将讨论 C++ 中的厌恶数，包括不同的方法和示例。

什么是厌恶数？

如果一个正数，其二进制展开中的置位（1）数量为奇数，则该数被认为是厌恶数。1 是第一个厌恶数，因为它等于(0001)，置位数量为奇数。任何可以写成 2 的幂（2^n）的数都将是厌恶数，因为这些数在二进制表示中将有1后面跟着零。因此，1是一个奇数，它可以是一个厌恶数。

前十个厌恶数是：1、2、4、7、10、11、13、14、16、19。

例如

输入

• 14

输出

• 厌恶数。
• 二进制展开：1110
• 这里有 3 个置位，3 是一个奇数。
• 因此，14 是一个厌恶数。

输入

• 25

输出

• 厌恶数。
• 二进制展开：11001
• 这里有 3 个置位，3 是一个奇数。
• 因此，25 是一个厌恶数。

输入

• 32

输出

• 不是厌恶数。
• 二进制展开：100000 (2^5)。
• 这里只有一个置位，1 是一个奇数。
• 32 是一个厌恶数。

方法 1：计算二进制表示中 1 的数量。

让我们举个例子来检查给定的数字是否是厌恶数

输出

说明

函数定义

• countOnes(int n)
  • 此函数确定整数在其二进制表示中有多少个置位（1）。
• isOdious(int n)
  • 此函数确定整数二进制表示中的置位计数是否为奇数。

countOnes(int n)

• 首先，将变量的计数设置为零。
• 接下来，重复将输入数字 n 除以二，依次遍历每个位。
• 如果 n 除以 2 的余数表示存在置位，则递增计数。
• 返回置位的总数。

IsOdious (int n)

• 它将调用countOnes()函数来查找给定整数 n 中置位的数量。
• 使用模运算（与 2 取模）来确定置位计数是否为奇数。

复杂度分析

时间复杂度

• 查找给定数字是否为厌恶数的时间复杂度为O(log n)。

空间复杂度

• 查找给定数字是否为厌恶数的空间复杂度为O(1)。

方法 2：使用位运算来计算置位。

让我们再举一个例子来检查给定的数字是否是厌恶数

输出

说明

函数定义

• countOnesBitwise(int n)
  • 此函数使用位运算来确定给定整数的二进制表示中存在多少个置位（1）。
• isOdious(int n)
• 此函数确定整数的二进制表示中置位计数是否为奇数。

countOnesBitwise

• 首先，将变量的计数设置为零。
• 接下来，使用与 1 的位 AND 运算来遍历输入数字 n 的每个位。
• 如果位 AND 运算表示存在置位且结果非零，则递增计数。
• 为了考虑下一个位，每次迭代时将 n 向右移一位。
• 返回置位的总数。

IsOdious 角色

• 调用countOnesBitwise函数来查找输入整数 n 中的置位数量。
• 使用模运算（与 2 取模）来确定置位计数是否为奇数。

复杂度分析

时间复杂度

• 查找给定数字是否为厌恶数的时间复杂度为O(log n)。

空间复杂度

• 查找给定数字是否为厌恶数的空间复杂度为O(1)。