duanbu4962 2015-04-06 22:01
浏览 47
已采纳

没有为数字golang设置位

I am trying to solve project euler problem 3 in golang:

The problem is as follows:

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

I am trying to solve it as follows:

package main

import (
    "fmt"
)

func primeset(n uint64) uint64 {
    primes := uint64(0)
    for p:= uint64(2);p <= n;p++ {
        if((primes & (1 << p)) == 0){
            fmt.Println("Current prime",p)
            for j:=uint64(2)*p;j <=n;j=j+p {
                fmt.Println("Current num:",j)
                primes |= (1 << j)
                fmt.Println("Bitset value is:",primes)
            }
        }
    }
    return primes
}

func main() {
    n := uint64(100)
    primes := primeset(n)
    fmt.Println("Primes is",primes)
    j := n
    for j >= 2 {
        s := primes & (1 << uint64(j))
        if((s == 0) && ((n % j) == 0)){
            fmt.Println("Largest factor",j)
            return
        } else {
            j--
        }
    }

}

In the function 'primeset', I start with an unsigned int called 'primes' with an initial value of 0 and then I left shift by a number(which is a composite) and set that bit of 'primes' to 1.

The idea is that I simply check the 4th bit of 'primes' to see if it has been set. If the bit is set, its not a prime.

For small numbers the code seems to work but when I started testing it for numbers such as 100, all of a sudden things were rather bizzare.

I noticed that the bit shifting is not working while trying to set it for the 62nd bit onwards. The following trace can demonstrate the situation:

Current num: 48
Bitset value is: 375299968947536
Current num: 50
Bitset value is: 1501199875790160
Current num: 52
Bitset value is: 6004799503160656
Current num: 54
Bitset value is: 24019198012642640
Current num: 56
Bitset value is: 96076792050570576
Current num: 58
Bitset value is: 384307168202282320
Current num: 60
Bitset value is: 1537228672809129296
Current num: 62
Bitset value is: 6148914691236517200
Current num: 64
Bitset value is: 6148914691236517200
Current num: 66
Bitset value is: 6148914691236517200
Current num: 68
Bitset value is: 6148914691236517200
Current num: 70
Bitset value is: 6148914691236517200
Current num: 72
Bitset value is: 6148914691236517200
Current num: 74
Bitset value is: 6148914691236517200
Current num: 76
Bitset value is: 6148914691236517200
Current num: 78
Bitset value is: 6148914691236517200
Current num: 80
Bitset value is: 6148914691236517200
Current num: 82
Bitset value is: 6148914691236517200
Current num: 84
Bitset value is: 6148914691236517200
Current num: 86
Bitset value is: 6148914691236517200

Can somebody point out what might be off with the way I am performing my bit operations?

Thanks

  • 写回答

1条回答 默认 最新

  • dongshi4589 2015-04-06 22:41
    关注

    The Go Programming Language Specification

    Arithmetic operators

    <<   left shift             integer << unsigned integer
    >>   right shift            integer >> unsigned integer
    

    The shift operators shift the left operand by the shift count specified by the right operand. They implement arithmetic shifts if the left operand is a signed integer and logical shifts if it is an unsigned integer. There is no upper limit on the shift count. Shifts behave as if the left operand is shifted n times by 1 for a shift count of n.

    You are shifting bits off the end of 64 bits: (1<<p) where p > 63. For example,

    package main
    
    import (
        "fmt"
    )
    
    func main() {
        primes := ^uint64(0)
        fmt.Println(primes)
        for _, p := range []uint64{0, 1, 2, 62, 63, 64, 65, 99, 100} {
            fmt.Println(p, "\t", primes&(1<<p))
        }
    }
    

    Output:

    18446744073709551615
    0    1
    1    2
    2    4
    62   4611686018427387904
    63   9223372036854775808
    64   0
    65   0
    99   0
    100  0
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题