{"id":606,"date":"2024-08-16T10:33:22","date_gmt":"2024-08-16T02:33:22","guid":{"rendered":"http:\/\/120.55.184.7\/?p=606"},"modified":"2025-05-03T05:44:55","modified_gmt":"2025-05-02T21:44:55","slug":"bitmap-%e8%af%a6%e8%a7%a3%e5%8f%8a-go-%e5%ae%9e%e7%8e%b0","status":"publish","type":"post","link":"https:\/\/beijian99.top\/?p=606","title":{"rendered":"Bitmap"},"content":{"rendered":"\n

\u4ec0\u4e48\u662f Bitmap<\/h2>\n\n\n\n

Bitmap\uff08\u4f4d\u56fe\uff09\u662f\u4e00\u79cd\u4f7f\u7528\u4f4d\u6570\u7ec4\u6765\u8868\u793a\u6570\u636e\u7684\u6570\u636e\u7ed3\u6784\uff0c\u6bcf\u4e2a\u4f4d(bit)\u53ef\u4ee5\u8868\u793a\u67d0\u79cd\u72b6\u6001\uff08\u901a\u5e38\u662f\u5b58\u5728\u6216\u4e0d\u5b58\u5728\uff09\u3002Bitmap \u4e3b\u8981\u7528\u4e8e\u9ad8\u6548\u5730\u5b58\u50a8\u548c\u64cd\u4f5c\u5927\u91cf\u5e03\u5c14\u503c\u6216\u6574\u6570\u96c6\u5408\u3002<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Bitmap \u7684\u4e3b\u8981\u7279\u70b9<\/h3>\n\n\n\n
    \n
  1. \u7a7a\u95f4\u6548\u7387<\/strong>\uff1a\u6bcf\u4e2a\u5143\u7d20\u53ea\u5360\u7528\u4e00\u4e2a bit\uff0c\u6bd4\u4f20\u7edf\u6570\u7ec4\u6216\u54c8\u5e0c\u8868\u66f4\u8282\u7701\u7a7a\u95f4<\/li>\n\n\n\n
  2. \u5feb\u901f\u64cd\u4f5c<\/strong>\uff1a\u4f4d\u8fd0\u7b97\u4f7f\u5f97\u96c6\u5408\u64cd\u4f5c\uff08\u5982\u5e76\u96c6\u3001\u4ea4\u96c6\uff09\u975e\u5e38\u9ad8\u6548<\/li>\n\n\n\n
  3. \u9002\u5408\u5bc6\u96c6\u6570\u636e<\/strong>\uff1a\u5f53\u6570\u636e\u8303\u56f4\u4e0d\u5927\u4f46\u6570\u91cf\u5f88\u591a\u65f6\u7279\u522b\u9ad8\u6548<\/li>\n<\/ol>\n\n\n\n

    Bitmap \u7684\u57fa\u672c\u64cd\u4f5c<\/h2>\n\n\n\n
      \n
    1. \u8bbe\u7f6e\u4f4d\uff08Set\uff09<\/strong>\uff1a\u5c06\u67d0\u4e00\u4f4d\u8bbe\u4e3a 1<\/li>\n\n\n\n
    2. \u6e05\u9664\u4f4d\uff08Clear\uff09<\/strong>\uff1a\u5c06\u67d0\u4e00\u4f4d\u8bbe\u4e3a 0<\/li>\n\n\n\n
    3. \u6d4b\u8bd5\u4f4d\uff08Test\uff09<\/strong>\uff1a\u68c0\u67e5\u67d0\u4e00\u4f4d\u662f\u5426\u4e3a 1<\/li>\n\n\n\n
    4. \u8ba1\u6570\uff08Count\uff09<\/strong>\uff1a\u7edf\u8ba1\u6240\u6709\u8bbe\u7f6e\u4e3a 1 \u7684\u4f4d\u6570<\/li>\n\n\n\n
    5. \u904d\u5386\uff08Iterate\uff09<\/strong>\uff1a\u904d\u5386\u6240\u6709\u8bbe\u7f6e\u4e3a 1 \u7684\u4f4d<\/li>\n<\/ol>\n\n\n\n

      Go \u8bed\u8a00\u5b9e\u73b0 Bitmap<\/h2>\n\n\n\n

      \u57fa\u7840\u5b9e\u73b0<\/h3>\n\n\n
      \npackage bitmap\n\nimport (\n    "errors"\n)\n\n\/\/ Bitmap \u7ed3\u6784\u4f53\ntype Bitmap struct {\n    data []uint64\n    size uint64\n}\n\n\/\/ NewBitmap \u521b\u5efa\u4e00\u4e2a\u65b0\u7684 Bitmap\nfunc NewBitmap(size uint64) *Bitmap {\n    \/\/ \u8ba1\u7b97\u9700\u8981\u591a\u5c11\u4e2a uint64 \u6765\u5b58\u50a8 size \u4e2a bit\n    length := (size + 63) \/ 64\n    return &Bitmap{\n        data: make([]uint64, length),\n        size: size,\n    }\n}\n\n\/\/ Set \u5c06\u6307\u5b9a\u4f4d\u8bbe\u7f6e\u4e3a 1\nfunc (b *Bitmap) Set(pos uint64) error {\n    if pos >= b.size {\n        return errors.New("position out of range")\n    }\n    index := pos \/ 64\n    offset := pos % 64\n    b.data[index] |= 1 << offset\n    return nil\n}\n\n\/\/ Clear \u5c06\u6307\u5b9a\u4f4d\u8bbe\u7f6e\u4e3a 0\nfunc (b *Bitmap) Clear(pos uint64) error {\n    if pos >= b.size {\n        return errors.New("position out of range")\n    }\n    index := pos \/ 64\n    offset := pos % 64\n    b.data[index] &^= 1 << offset\n    return nil\n}\n\n\/\/ Test \u68c0\u67e5\u6307\u5b9a\u4f4d\u662f\u5426\u4e3a 1\nfunc (b *Bitmap) Test(pos uint64) (bool, error) {\n    if pos >= b.size {\n        return false, errors.New("position out of range")\n    }\n    index := pos \/ 64\n    offset := pos % 64\n    return (b.data[index] & (1 << offset)) != 0, nil\n}\n\n\/\/ Count \u7edf\u8ba1\u6240\u6709\u8bbe\u7f6e\u4e3a 1 \u7684\u4f4d\u6570\nfunc (b *Bitmap) Count() uint64 {\n    var count uint64\n    for _, num := range b.data {\n        \/\/ \u4f7f\u7528 Brian Kernighan \u7b97\u6cd5\u8ba1\u7b97\u4e00\u4e2a\u6570\u4e2d 1 \u7684\u4f4d\u6570\n        for num != 0 {\n            num &= num - 1\n            count++\n        }\n    }\n    return count\n}\n\n\/\/ Size \u8fd4\u56de Bitmap \u7684\u603b\u5927\u5c0f\uff08\u4f4d\u6570\uff09\nfunc (b *Bitmap) Size() uint64 {\n    return b.size\n}\n\n\/\/ Reset \u5c06\u6240\u6709\u4f4d\u91cd\u7f6e\u4e3a 0\nfunc (b *Bitmap) Reset() {\n    for i := range b.data {\n        b.data[i] = 0\n    }\n}\n\n\/\/ And \u4e0e\u53e6\u4e00\u4e2a Bitmap \u8fdb\u884c\u6309\u4f4d\u4e0e\u64cd\u4f5c\nfunc (b *Bitmap) And(other *Bitmap) error {\n    if b.size != other.size {\n        return errors.New("bitmaps have different sizes")\n    }\n    for i := range b.data {\n        b.data[i] &= other.data[i]\n    }\n    return nil\n}\n\n\/\/ Or \u4e0e\u53e6\u4e00\u4e2a Bitmap \u8fdb\u884c\u6309\u4f4d\u6216\u64cd\u4f5c\nfunc (b *Bitmap) Or(other *Bitmap) error {\n    if b.size != other.size {\n        return errors.New("bitmaps have different sizes")\n    }\n    for i := range b.data {\n        b.data[i] |= other.data[i]\n    }\n    return nil\n}\n\n\/\/ Xor \u4e0e\u53e6\u4e00\u4e2a Bitmap \u8fdb\u884c\u6309\u4f4d\u5f02\u6216\u64cd\u4f5c\nfunc (b *Bitmap) Xor(other *Bitmap) error {\n    if b.size != other.size {\n        return errors.New("bitmaps have different sizes")\n    }\n    for i := range b.data {\n        b.data[i] ^= other.data[i]\n    }\n    return nil\n}\n\n\/\/ Not \u5bf9\u6240\u6709\u4f4d\u8fdb\u884c\u53d6\u53cd\u64cd\u4f5c\nfunc (b *Bitmap) Not() {\n    for i := range b.data {\n        b.data[i] = ^b.data[i]\n    }\n    \/\/ \u5904\u7406\u6700\u540e\u4e00\u4e2a uint64 \u53ef\u80fd\u672a\u4f7f\u7528\u7684\u4f4d\n    if b.size%64 != 0 {\n        unusedBits := 64 - b.size%64\n        lastIndex := len(b.data) - 1\n        b.data[lastIndex] &= ^uint64(0) >> unusedBits\n    }\n}\n\n\/\/ ToSlice \u5c06\u6240\u6709\u8bbe\u7f6e\u4e3a 1 \u7684\u4f4d\u8f6c\u6362\u4e3a\u5207\u7247\nfunc (b *Bitmap) ToSlice() []uint64 {\n    var result []uint64\n    for i := uint64(0); i < b.size; i++ {\n        if val, _ := b.Test(i); val {\n            result = append(result, i)\n        }\n    }\n    return result\n}\n<\/pre><\/div>\n\n\n
      \u4f7f\u7528\u793a\u4f8b<\/h3>\n\n\n
      \npackage main\n\nimport (\n    "fmt"\n    "bitmap" \/\/ \u5047\u8bbe\u4e0a\u9762\u7684\u4ee3\u7801\u4fdd\u5b58\u5728 bitmap \u5305\u4e2d\n)\n\nfunc main() {\n    \/\/ \u521b\u5efa\u4e00\u4e2a\u80fd\u5b58\u50a8 1000 \u4e2a\u4f4d\u7684 Bitmap\n    bm := bitmap.NewBitmap(1000)\n\n    \/\/ \u8bbe\u7f6e\u4e00\u4e9b\u4f4d\n    bm.Set(1)\n    bm.Set(2)\n    bm.Set(3)\n    bm.Set(100)\n    bm.Set(999)\n\n    \/\/ \u6d4b\u8bd5\u4f4d\n    fmt.Println(bm.Test(1))   \/\/ true\n    fmt.Println(bm.Test(4))   \/\/ false\n    fmt.Println(bm.Test(999)) \/\/ true\n\n    \/\/ \u7edf\u8ba1\n    fmt.Println("Count:", bm.Count()) \/\/ 5\n\n    \/\/ \u8f6c\u6362\u4e3a\u5207\u7247\n    fmt.Println("Set bits:", bm.ToSlice()) \/\/ [1 2 3 100 999]\n\n    \/\/ \u6e05\u9664\u4f4d\n    bm.Clear(2)\n    fmt.Println(bm.Test(2)) \/\/ false\n\n    \/\/ \u521b\u5efa\u53e6\u4e00\u4e2a Bitmap \u5e76\u8fdb\u884c\u4f4d\u8fd0\u7b97\n    bm2 := bitmap.NewBitmap(1000)\n    bm2.Set(2)\n    bm2.Set(3)\n    bm2.Set(4)\n\n    bm.Or(bm2)\n    fmt.Println("After OR:", bm.ToSlice()) \/\/ [1 2 3 4 100 999]\n\n    bm.And(bm2)\n    fmt.Println("After AND:", bm.ToSlice()) \/\/ [2 3 4]\n\n    \/\/ \u53d6\u53cd\n    bm.Not()\n    fmt.Println("After NOT:", bm.ToSlice()) \/\/ [0 1 5 6 ... 999] (\u9664\u4e86 2,3,4 \u7684\u6240\u6709\u4f4d)\n}\n<\/pre><\/div>\n\n\n
      \u6027\u80fd\u4f18\u5316\u8003\u8651<\/h2>\n\n\n\n
        \n
      1. \u6279\u91cf\u64cd\u4f5c<\/strong>\uff1a\u5bf9\u4e8e\u8fde\u7eed\u4f4d\u7684\u8bbe\u7f6e\/\u6e05\u9664\uff0c\u53ef\u4ee5\u5b9e\u73b0\u6279\u91cf\u64cd\u4f5c\u6765\u63d0\u9ad8\u6027\u80fd<\/li>\n\n\n\n
      2. \u5e76\u884c\u5904\u7406<\/strong>\uff1a\u5bf9\u4e8e\u5927\u578b Bitmap\uff0c\u53ef\u4ee5\u4f7f\u7528 goroutine \u5e76\u884c\u5904\u7406\u4e0d\u540c\u7684 uint64 \u5757<\/li>\n\n\n\n
      3. \u538b\u7f29\u5b58\u50a8<\/strong>\uff1a\u5bf9\u4e8e\u7a00\u758f Bitmap\uff0c\u53ef\u4ee5\u8003\u8651\u4f7f\u7528\u538b\u7f29\u5b58\u50a8\u683c\u5f0f\u5982 RLE (Run-Length Encoding)<\/li>\n<\/ol>\n\n\n\n
        \u5e94\u7528\u573a\u666f<\/h2>\n\n\n\n
          \n
        1. \u5927\u6570\u636e\u53bb\u91cd<\/strong>\uff1a\u5feb\u901f\u5224\u65ad\u5143\u7d20\u662f\u5426\u5b58\u5728<\/li>\n\n\n\n
        2. \u5e03\u9686\u8fc7\u6ee4\u5668<\/strong>\uff1aBitmap \u662f\u5e03\u9686\u8fc7\u6ee4\u5668\u7684\u57fa\u7840\u7ec4\u4ef6<\/li>\n\n\n\n
        3. \u6743\u9650\u7cfb\u7edf<\/strong>\uff1a\u7528\u4f4d\u8868\u793a\u4e0d\u540c\u6743\u9650<\/li>\n\n\n\n
        4. \u6570\u636e\u5e93\u7d22\u5f15<\/strong>\uff1a\u67d0\u4e9b\u6570\u636e\u5e93\u4f7f\u7528 Bitmap \u7d22\u5f15\u52a0\u901f\u67e5\u8be2<\/li>\n\n\n\n
        5. \u56fe\u50cf\u5904\u7406<\/strong>\uff1a\u4e8c\u503c\u56fe\u50cf\u53ef\u4ee5\u7528 Bitmap \u8868\u793a<\/li>\n<\/ol>\n\n\n\n
          \u6269\u5c55\uff1aRoaring Bitmap<\/h2>\n\n\n\n
          \u5bf9\u4e8e\u66f4\u9ad8\u7ea7\u7684 Bitmap \u5b9e\u73b0\uff0c\u53ef\u4ee5\u8003\u8651 Roaring Bitmap\uff0c\u5b83\u7ed3\u5408\u4e86\u6570\u7ec4\u3001Bitmap \u548c Run-Length Encoding\uff0c\u9002\u5408\u5904\u7406\u7a00\u758f\u548c\u5bc6\u96c6\u6570\u636e\u6df7\u5408\u7684\u573a\u666f\u3002<\/p>\n\n\n\n
          \u5f00\u6e90\u5b9e\u73b0 http:\/\/github.com\/RoaringBitmap\/roaring<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
          \u4ec0\u4e48\u662f Bitmap Bitmap\uff08\u4f4d\u56fe\uff09\u662f\u4e00\u79cd\u4f7f\u7528\u4f4d\u6570\u7ec4\u6765\u8868\u793a\u6570\u636e\u7684\u6570\u636e\u7ed3\u6784\uff0c\u6bcf\u4e2a\u4f4d(bit)\u53ef\u4ee5\u8868\u793a\u67d0\u79cd\u72b6 […]<\/p>\n","protected":false},"author":1,"featured_media":987,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[4],"tags":[],"class_list":["post-606","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithm"],"_links":{"self":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/606","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=606"}],"version-history":[{"count":4,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/606\/revisions"}],"predecessor-version":[{"id":988,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/606\/revisions\/988"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/media\/987"}],"wp:attachment":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=606"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=606"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=606"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}