如何检查二进制数是否可被 3 整除

2025年3月17日 | 阅读11分钟

问题是检查给定的二进制数是否能被 3 整除，或者是否是 3 的倍数。

这个问题在编程界非常流行，并被亚马逊、微软、Adobe 等公司在软件工程面试中提问。

二进制数可以是字符串形式或整数形式。在进行实现之前，我们还需要注意这一点。

示例 1

binary = "0011"
Output = True

Explanation: The given binary number is 3 in decimal, which is obviously divisible by 3.

示例 2

binary = "1011"
Output = False

Explanation: The given binary number is 11 in decimal, which is not a multiple of 3.

在本文中，我们将学习解决此问题的不同方法，并讨论检查二进制数是否是三的倍数的最佳方法。

方法 1 - 转换为十进制

最简单的方法是将二进制数转换为十进制等效数。然后检查它是否能被 3 整除。

将二进制数转换为十进制

从右到左遍历数字。
将每个数字乘以 2，2 的幂为其位置。
对每次迭代的结果求和。

检查该数字是否能被 3 整除；如果能，则该二进制数也能被 3 整除。

下面是相同的 Python 实现

"""
Python program to check if a binary number is
divisible by 3
"""

# Function
def is_divisible_by_three(binary):
    ans = 0
    i = 1

    # Iterating through the binary number digits
    while binary > 0:
        
        # Extracting the rightmost digit and
        # multiplying it by the corresponding power of 2
        ans = ans + i * (binary % 10)
        
        # Removing the rightmost digit
        binary = binary // 10
        
        # Updating the power of 2 for the next digit
        i = i * 2

    # Checking if the sum is divisible by 3
    if ans % 3 == 0:
        return True

    return False

# Binary Numbers
binary1 = 11		# 3 in decimal
binary2 = 1100	# 12 in decimal
binary3 = 1011	# 11 in decimal

# Checking divisibility for binary1
print(f"Is binary1 = {binary1} divisible by 3? {is_divisible_by_three(binary1)}")

# Checking divisibility for binary2
print(f"Is binary2 = {binary2} divisible by 3? {is_divisible_by_three(binary2)}")

# Checking divisibility for binary3
print(f"Is binary3 = {binary3} divisible by 3? {is_divisible_by_three(binary3)}")

输出

Is binary1 = 11 divisible by 3? True
Is binary2 = 1100 divisible by 3? True
Is binary3 = 1011 divisible by 3? False

时间复杂度 = O(n)： 其中 n 是二进制数中的位数。

空间复杂度 - O(1)： 它使用常量空间。

方法 2 - 使用 DFA（确定性有限自动机） - 状态机方法

一种更有效的方法是设计一个模拟除法过程的 DFA。

状态机或 DFA 将有三个状态：0、1 和 2，分别表示二进制数除以三的余数。

DFA 的图示表示如下

How to Check if a Binary Number is Divisible by 3

我们将从初始状态 0 开始，并从左到右迭代二进制位，根据转换更新状态

如果当前状态为 0
- 如果数字为 0，状态保持为 0 - 转换：状态 0 -> 状态 0
- 如果数字为 1，我们移动到下一个状态 1 - 转换：状态 0 -> 状态 1
如果当前状态为 1
- 如果数字为 0，我们移动到状态 2 - 转换：状态 1 -> 状态 2
- 如果数字为 1，我们回到状态 0 - 转换：状态 1 -> 状态 0
如果当前状态为 2
- 如果数字为 1，我们循环到状态 2 - 转换：状态 2 -> 状态 2
- 如果数字为 0，我们回到状态 1 - 转换：状态 2 -> 状态 1

遍历所有数字后，如果最终状态为 0，则二进制数能被三整除，我们返回 True。否则，返回 False。

下面是相同的 Python 实现

"""
Python program to check if a binary number is
divisible by 3 using DFA
"""

# Function
def is_divisible_by_three(binary):
    state = '0'

    # Iterating through the binary number digits
    for i in binary:
        
        # Using pattern matching to determine the next state
        # based on the current state and the current binary digit
        match state:
            # If the current state is 0
            case '0':
                if i == '1':
                    state = '1'

            # If the current state is 1
            case '1':
                if i == '1':
                    state = '0'
                else:
                    state = '2'

            # If the current state is 2
            case '2':
                if i == '0':
                    state = '1'

    # Checking the final state
    if state == '0':
        return True
    
    return False

# Binary Numbers
binary1 = '11' 	# 3 in decimal
binary2 = '1100' 	# 12 in decimal
binary3 = '1011'	# 11 in decimal

# Checking divisibility for binary1
print(f"Is binary1 = {binary1} divisible by 3? {is_divisible_by_three(binary1)}")

# Checking divisibility for binary2
print(f"Is binary2 = {binary2} divisible by 3? {is_divisible_by_three(binary2)}")

# Checking divisibility for binary3
print(f"Is binary3 = {binary3} divisible by 3? {is_divisible_by_three(binary3)}")

输出

Is binary1 = 11 divisible by 3? True
Is binary2 = 1100 divisible by 3? True
Is binary3 = 1011 divisible by 3? False

时间复杂度 = O(n)： 其中 n 是二进制数中的位数。

空间复杂度 - O(1)： 它使用常量空间用于状态变量。

但这种方法不是最有效的，也需要先前的自动机知识。

方法 3 - 位操作 - (|奇数位 - 偶数位|) 能被 3 整除

这是确定二进制数是否能被三整除的最有效且优雅的方法。

我们将分别计算奇数位置和偶数位置的 1 的数量。

如果这些计数的差能被三整除，则二进制数能被三整除。

一般来说，二进制数 N 可以表示为

N = b_n 2^n-1+ b_n-1 2^n-2+ b_n-22^n-3+ … + b₂2² + b₁2¹ + b₀2⁰

其中 bi 表示二进制位（0 或 1），n 表示 2 的最高次幂。

现在，让我们检查每个 2 的幂除以 3 的余数

2^0 % 3 = 1
2^1 % 3 = 2 
2^2 % 3 = 1
2^3 % 3 = 2 
2^4 % 3 = 1
...

我们可以观察到，随着 2 的幂增加，余数在 1 和 2 之间交替。

根据上述模式，表达式 (2^k) % 3 可以简化如下

- If k is even, (2^k) % 3 = 1
- If k is odd, (2^k) % 3 = 2

因此，对于一个二进制数要能被 3 整除，偶数位置和奇数位置的 1 的数量之差必须能被 3 整除。

在十进制系统中，如果一个数字的各位数字之和能被三整除，那么这个数字也能被 3 整除。另一种方法是对于偶数位置的 1，我们计数为 2，对于奇数位置的 1，我们计数为 1

如果计数能被 3 整除。那么二进制数就能被 3 整除。

位操作的 Python 实现如下

在我们的方法中，我们分别计算偶数位置和奇数位置的 1 的数量，并检查它们的差是否能被 3 整除。如果能，则二进制数能被三整除。否则，不能整除。

"""
Python program to check if a binary number is
divisible by 3 using Bit Manipulation.
"""

# Function
def is_divisible_by_three(binary):

    # Get the length of the binary number
    n = len(binary)

    # Flag to keep track of odd/even positions
    odd_position = True

    # Variables to count the number of ones
    # at even and odd positions
    ones_at_even = 0
    ones_at_odd = 0

    # Iterate through the binary number left-to-right
    for i in range(n-1, -1, -1):

        # If it's an odd position
        if odd_position:
            # Check if the digit is 1 and
            # increment the count of ones at odd positions
            if binary[i] == '1':
                ones_at_odd += 1

            # Set the flag to move to even position
            odd_position = False

            # Skip to the next iteration
            continue

        # If it's an even position
        if not odd_position:
            # Check if the digit is 1 and increment
            # the count of ones at even positions
            if binary[i] == '1':
                ones_at_even += 1

            # Set the flag to move to odd position
            odd_position = True

    # Check if the difference between the counts
    # of ones at even and odd positions is divisible by 3
    return (ones_at_even - ones_at_odd) % 3 == 0

# Binary Numbers
binary1 = '11' # 3 in decimal
binary2 = '1100' # 12 in decimal
binary3 = '1011' # 11 in decimal

# Checking divisibility for binary1
print(f"Is binary1 = {binary1} divisible by 3? {is_divisible_by_three(binary1)}")

# Checking divisibility for binary2
print(f"Is binary2 = {binary2} divisible by 3? {is_divisible_by_three(binary2)}")

# Checking divisibility for binary3
print(f"Is binary3 = {binary3} divisible by 3? {is_divisible_by_three(binary3)}")

输出

Is binary1 = 11 divisible by 3? True
Is binary2 = 1100 divisible by 3? True
Is binary3 = 1011 divisible by 3? False

说明

在上面的示例中，我们从右到左（从最低有效位到最高有效位）遍历二进制数。
odd_position 最初设置为 True
- 一旦我们在奇数位置，我们检查该数字是否为 '1'。如果为 '1'，我们递增 ones_at_odd 1。
- 然后，我们将 odd_position 设置为 False，表示下一个索引将是偶数。
如果 odd_position 设置为 False，则表示我们在偶数索引处
- 我们检查该数字是否为 '1'。如果为 '1'，我们递增 ones_at_even 1。
- 然后，我们将 odd_position 设置为 True，表示下一个索引将是奇数。
循环完成后，我们计算偶数位置和奇数位置的 1 的数量之差 (ones_at_even - ones_at_odd)。
最后，我们检查这个差是否能被 3 整除 ((ones_at_even - ones_at_odd) % 3 == 0)。
如果差能被 3 整除，我们返回 True，表示二进制数能被三整除。否则，我们返回 False。

时间复杂度 = O(n)， 其中 n 是二进制数中的位数。

空间复杂度 = O(1) 因为我们只需要几个变量来存储计数器。

最佳方法

在讨论的方法中，位操作方法是检查二进制数是否能被三整除的最有效方法。
这种方法易于理解，避免了转换为十进制，并直接对二进制数进行操作。

C++ 实现

// C++ program to check if a binary number
// is divisible by 3 using bit manipulation
#include <iostream>
#include <string>
using namespace std;

// Function
bool is_divisible_by_three(string binary) {
    
    // Get the length of the string
    int n = binary.length();
    
    // Falg to keep track of odd/even positions
    bool odd_position = true;
    
    // Variables to count ones at even/odd positions
    int ones_at_even = 0;
    int ones_at_odd = 0;
    
    // Iterate through the binary number left-to-right
    for (int i = n - 1; i >= 0; i--) {
        
        
        // If it's an odd position
        if (odd_position) {
            // Check if the digit is 1 and
            // increment the count of ones at odd positions
            if (binary[i] == '1') {
                ones_at_odd++;
            }
            
            // Set the flag to move to even position
            odd_position = false;
            continue;
        }
        
        // If it's an even position
        if (!odd_position) {
            // Check if the digit is 1 and increment
            // the count of ones at even positions
            if (binary[i] == '1') {
                ones_at_even++;
            }
            
            // Set the flag to move to odd position
            odd_position = true;
        }
    }
    // Check if the difference between the counts
    // of ones at even and odd positions is divisible by 3
    return (ones_at_even - ones_at_odd) % 3 == 0;
}

// Driver function
int main() {
    string binary1 = "11"; // 3 in decimal
    string binary2 = "1100"; // 12 in decimal
    string binary3 = "1011"; // 11 in decimal

    // Checking divisibility for binary1
    cout << "Is binary1 = " << binary1 << " divisible by 3? " << boolalpha << is_divisible_by_three(binary1) << endl;

    // Checking divisibility for binary2
    cout << "Is binary2 = " << binary2 << " divisible by 3? " << boolalpha << is_divisible_by_three(binary2) << endl;

    // Checking divisibility for binary3
    cout << "Is binary3 = " << binary3 << " divisible by 3? " << boolalpha << is_divisible_by_three(binary3) << endl;

    return 0;
}

输出

C 语言实现

// C program to check if a binary number
// is divisible by 3 using bit manipulation
#include <stdio.h>
#include <stdbool.h>
#include <string.h>

// Function
bool is_divisible_by_three(char* binary) {
    
    // Get the length of the string
    int n = strlen(binary);
    
    // Falg to keep track of odd/even positions
    bool odd_position = true;
    
    // Variables to count ones at even/odd positions
    int ones_at_even = 0;
    int ones_at_odd = 0;
    
    // Iterate through the binary number left-to-right
    for (int i = n - 1; i >= 0; i--) {
        
        // If it's an odd position
        if (odd_position) {
            // Check if the digit is 1 and
            // increment the count of ones at odd positions
            if (binary[i] == '1') {
                ones_at_odd++;
            }
            
            // Set the flag to move to even position
            odd_position = false;
            continue;
        }
        
        // If it's an even position
        if (!odd_position) {
            // Check if the digit is 1 and increment
            // the count of ones at even positions
            if (binary[i] == '1') {
                ones_at_even++;
            }
            
            // Set the flag to move to odd position
            odd_position = true;
        }
    }
    // Check if the difference between the counts
    // of ones at even and odd positions is divisible by 3
    return (ones_at_even - ones_at_odd) % 3 == 0;
}

// Driver Function
int main() {
    char binary1[] = "11"; // 3 in decimal
    char binary2[] = "1100"; // 12 in decimal
    char binary3[] = "1011"; // 11 in decimal

    // Checking divisibility for binary1
    printf("Is binary1 = %s divisible by 3? %s\n", binary1, is_divisible_by_three(binary1) ? "true" : "false");

    // Checking divisibility for binary2
    printf("Is binary2 = %s divisible by 3? %s\n", binary2, is_divisible_by_three(binary2) ? "true" : "false");

    // Checking divisibility for binary3
    printf("Is binary3 = %s divisible by 3? %s\n", binary3, is_divisible_by_three(binary3) ? "true" : "false");

    return 0;
}

输出

结论

我们可以使用各种方法来检查二进制数是否能被三整除。

我们可以将二进制数转换为其十进制等效数，然后检查它是否能被 3 整除。
另一种方法是设计一个模拟除法过程的 DFA。DFA 将有三个状态，0、1 和 2，表示除以 3 时的余数。如果我们最终停在状态 0。那么我们可以说该二进制数能被 3 整除。
最有效的方法是确定奇数位置和偶数位置的 1 的数量之差。如果差能被三整除，则二进制数也能被 3 整除。

我们可以使用最后一种方法以线性时间复杂度解决问题。此外，这也是检查二进制数是否能被三整除的推荐方法。

下一主题股票买卖问题

如何检查二进制数是否可被 3 整除

示例 1

示例 2

方法 1 - 转换为十进制

方法 2 - 使用 DFA（确定性有限自动机） - 状态机方法

方法 3 - 位操作 - (|奇数位 - 偶数位|) 能被 3 整除

最佳方法

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

如何检查二进制数是否可被 3 整除

示例 1

示例 2

方法 1 - 转换为十进制

方法 2 - 使用 DFA（确定性有限自动机） - 状态机方法

方法 3 - 位操作 - (|奇数位 - 偶数位|) 能被 3 整除

最佳方法

结论

相关帖子

打印二叉树的左视图

设计和实现特殊栈数据结构

2-3 树 (搜索、插入和删除)

生成所有子数组

Hopcroft-Karp 算法用于最大匹配

原始数据结构

二叉索引树

第 k1 小和第 k2 小元素之间的元素之和

C++ 中的队列数组实现

连续子数组最大和 (Kadane 算法)

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器