Goメモ-495 (シンプルなビットベクタ)(BitVector)

関連記事

GitHub - devlights/blog-summary: ブログ「いろいろ備忘録日記」のまとめ

概要

以下、自分用のメモです。

たまに、ビットベクタ（BitVector, BitArrayとも言う）を使いたいときがあります。で、何回も同じ処理を書いている気がしたので、ついでにここにメモメモ。。。

サンプル

bitvector.go

package main

import (
    "fmt"
    "strings"
)

type (
    // BitVector は、ビットベクタを表す構造体です.
    BitVector struct {
        bits []uint32
        size int
    }
    opcode int
)

const (
    AND opcode = iota
    OR  opcode = iota
    XOR opcode = iota
)

// NewBitVector は、指定されたサイズのビットベクタを作成します.
func NewBitVector(size int) *BitVector {
    return &BitVector{
        bits: make([]uint32, (size+31)/32),
        size: size,
    }
}

// Set は、指定されたインデックス位置のビットを設定します.
func (me *BitVector) Set(index int, value bool) error {
    if index < 0 || index >= me.size {
        return fmt.Errorf("index out of range: %d", index)
    }

    var (
        aryIndex = index / 32
        bitIndex = uint(index % 32)
    )
    if value {
        me.bits[aryIndex] |= 1 << bitIndex // ビットオン (OR)
    } else {
        me.bits[aryIndex] &^= 1 << bitIndex // ビットクリア (AND NOT)
    }

    return nil
}

// Get は、指定されたインデックス位置のビットを取得します.
func (me *BitVector) Get(index int) (bool, error) {
    if index < 0 || index >= me.size {
        return false, fmt.Errorf("index out of range: %d", index)
    }

    var (
        aryIndex = index / 32
        bitIndex = uint(index % 32)
        bit      = (me.bits[aryIndex] & (1 << bitIndex)) != 0
    )

    return bit, nil
}

// And は、指定された *BitVector とのAND結果を設定した新たな *BitVector を返します.
func (me *BitVector) And(other *BitVector) (*BitVector, error) {
    return me.calc(other, AND)
}

// Or は、指定された *BitVector とのOR結果を設定した新たな *BitVector を返します.
func (me *BitVector) Or(other *BitVector) (*BitVector, error) {
    return me.calc(other, OR)
}

// Xor は、指定された *BitVector とのXOR結果を設定した新たな *BitVector を返します.
func (me *BitVector) Xor(other *BitVector) (*BitVector, error) {
    return me.calc(other, XOR)
}

func (me *BitVector) calc(other *BitVector, op opcode) (*BitVector, error) {
    if me.size != other.size {
        return nil, fmt.Errorf("size mismatch: %d != %d", me.size, other.size)
    }

    var (
        result  = NewBitVector(me.size)
        arySize = (me.size + 31) / 32
    )
    for i := range arySize {
        switch op {
        case AND:
            result.bits[i] = me.bits[i] & other.bits[i]
        case OR:
            result.bits[i] = me.bits[i] | other.bits[i]
        case XOR:
            result.bits[i] = me.bits[i] ^ other.bits[i]
        default:
            return nil, fmt.Errorf("unknown kind: %d", op)
        }
    }

    return result, nil
}

// String は、ビットベクタの文字列表現を返します.
func (me *BitVector) String() string {
    var (
        sb  strings.Builder
        val bool
    )
    for i := range me.size {
        val, _ = me.Get(i)
        if val {
            sb.WriteRune('1')
        } else {
            sb.WriteRune('0')
        }
    }

    return sb.String()
}

main.go

package main

import (
    "context"
    "errors"
    "log"
    "time"
)

const (
    MainTimeout = 100 * time.Millisecond
    ProcTimeout = 500 * time.Microsecond
)

var (
    ErrMainTooSlow = errors.New("[MAIN] TOO SLOW")
    ErrProcTooSlow = errors.New("[PROC] TOO SLOW")
)

func init() {
    log.SetFlags(0)
}

func main() {
    var (
        rootCtx          = context.Background()
        mainCtx, mainCxl = context.WithTimeoutCause(rootCtx, MainTimeout, ErrMainTooSlow)
        procCtx          = run(mainCtx)
        err              error
    )
    defer mainCxl()

    select {
    case <-mainCtx.Done():
        err = context.Cause(mainCtx)
    case <-procCtx.Done():
        if err = context.Cause(procCtx); errors.Is(err, context.Canceled) {
            err = nil
        }
    }

    if err != nil {
        log.Fatal(err)
    }
}

func run(pCtx context.Context) context.Context {
    var (
        ctx, cxl = context.WithCancelCause(pCtx)
    )

    go func() {
        cxl(proc(ctx))
    }()
    go func() {
        <-time.After(ProcTimeout)
        cxl(ErrProcTooSlow)
    }()

    return ctx
}

func proc(_ context.Context) error {
    const (
        bitSize = 32
    )

    //
    // ビットの設定
    //
    var (
        bv  = NewBitVector(bitSize)
        err error
    )

    for _, i := range []int{1, 3, 23} {
        if err = bv.Set(i, true); err != nil {
            return err
        }
    }
    log.Printf("ORIG : %s", bv)

    //
    // ビットの取得
    //
    var (
        bits []bool
        bit  bool
    )

    for _, i := range []int{1, 2, 3, 4} {
        if bit, err = bv.Get(i); err != nil {
            return err
        }

        bits = append(bits, bit)
    }
    log.Printf("BITS : %v", bits)

    //
    // 別のビットベクタとの演算
    //
    var (
        bv2   = NewBitVector(bitSize)
        bvAnd *BitVector
        bvOr  *BitVector
        bvXor *BitVector
    )

    for _, i := range []int{2, 23, 24} {
        if err = bv2.Set(i, true); err != nil {
            return err
        }
    }
    log.Printf("OTHER: %s", bv2)

    // AND
    if bvAnd, err = bv.And(bv2); err != nil {
        return err
    }
    log.Printf("AND  : %s", bvAnd)

    // OR
    if bvOr, err = bv.Or(bv2); err != nil {
        return err
    }
    log.Printf("OR   : %s", bvOr)

    // XOR
    if bvXor, err = bv.Xor(bv2); err != nil {
        return err
    }
    log.Printf("XOR  : %s", bvXor)

    return nil
}

Taskfile.yml

# https://taskfile.dev

version: '3'

tasks:
  default:
    cmds:
      - go run .

実行

$ task
task: [default] go run .
ORIG : 01010000000000000000000100000000
BITS : [true false true false]
OTHER: 00100000000000000000000110000000
AND  : 00000000000000000000000100000000
OR   : 01110000000000000000000110000000
XOR  : 01110000000000000000000010000000

参考情報

github.com

Goのおすすめ書籍

初めてのGo言語 ―他言語プログラマーのためのイディオマティックGo実践ガイド

実用 Go言語 ―システム開発の現場で知っておきたいアドバイス

Go言語による並行処理

Go言語 100Tips ありがちなミスを把握し、実装を最適化する impress top gearシリーズ

Goならわかるシステムプログラミング 第2版

効率的なGo ―データ指向によるGoアプリケーションの性能最適化

---

過去の記事については、以下のページからご参照下さい。

• ブログ 「いろいろ備忘録日記」の記事まとめ | ブログ「いろいろ備忘録日記」のまとめ

サンプルコードは、以下の場所で公開しています。

• GitHub - devlights/try-golang: This is my TUTORIAL project for golang.
• GitHub - devlights/try-python: This is my TUTORIAL project for Python.
• GitHub - devlights/try-csharp: This is my TUTORIAL project for C#.