首页 > 数学相关 > 数论应用 > 位运算(1)-检测一个数能否被3整除
2014
03-30

位运算(1)-检测一个数能否被3整除

第一个解决方案就是小学就学过的,如果一个数的每个位相加之和能被3整除,则这个数就可以被3整除。例如612各位之和为9,则可以被3整除。但是这个解决方法并不高效,我们需要取得每一位,然后再一个个相加。

观察二进制,我们可以找到一个模式来判断一个数能否被3整除。如果所有的偶数位出现1的次数为 even_count, 奇数位出现1的次数为 odd_count,两者只差如果是3的倍数,那么这个数就是3倍数。

例如:23 (00…..0010111)  even_count=3, odd_count = 1.    3-1 不能被2整除,所以不是3的倍数。

#include<stdio.h>

/* 返回n是否是3的倍数*/
int isMultipleOf3(int n)
{
    int odd_count = 0;
    int even_count = 0;

    /* 使n为正数,防止递归不退出*/
    if(n < 0)   n = -n;
    if(n == 0) return 1;
    if(n <= 2) return 0;

    while(n)
    {
        /* 统计偶数位有1的个数 */
        if(n & 1) 
           odd_count++;
        n = n>>1;

        /* 统计奇数位 */
        if(n & 1)
            even_count++;
        n = n>>1;
    }

     return isMultipleOf3(odd_count - even_coun));
}

/* 测试 */
int main()
{
    int num = 23;
    if (isMultipleOf3(num))    
        printf("num is multiple of 3");
    else
        printf("num is not a multiple of 3");
    getchar();
    return 0;
}

时间复杂度:O(logn)


  1. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?

  2. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  3. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?