Go语言实现位图排序(bitmap)

xcltapestry · · 4266 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

     Go语言提供了byte类型,一个byte对应8个位,所以转换一下就可以实现位图了。

    代码:    

package main

//author:xcl
//date:2014-1-25

import (
	"fmt"
)

func main() {
	arrInt32 := [...]uint32{5, 4, 2, 1, 3, 17, 13}

	var arrMax uint32 = 20
	bit := NewBitmap(arrMax)

	for _, v := range arrInt32 {
		bit.Set(v)
	}

	fmt.Println("排序后:")
	for i := uint32(0); i < arrMax; i++ {
		if k := bit.Test(i); k == 1 {
			fmt.Printf("%d ", i)
		}
	}
}

const (
	BitSize = 8 //一个字节8位
)

type Bitmap struct {
	BitArray  []byte
	ArraySize uint32
}

func NewBitmap(max uint32) *Bitmap {
	var r uint32
	switch {
	case max <= BitSize:
		r = 1
	default:
		r = max / BitSize
		if max%BitSize != 0 {
			r += 1
		}
	}

	fmt.Println("数组大小:", r)
	return &Bitmap{BitArray: make([]byte, r), ArraySize: r}
}

func (bitmap *Bitmap) Set(i uint32) {
	idx, pos := bitmap.calc(i)
	bitmap.BitArray[idx] |= 1 << pos
	fmt.Println("set()  value=", i, " idx=", idx, " pos=", pos, ByteToBinaryString(bitmap.BitArray[idx]))
}

func (bitmap *Bitmap) Test(i uint32) byte {
	idx, pos := bitmap.calc(i)
	return bitmap.BitArray[idx] >> pos & 1
}

func (bitmap *Bitmap) Clear(i uint32) {
	idx, pos := bitmap.calc(i)
	bitmap.BitArray[idx] &^= 1 << pos
}

func (bitmap *Bitmap) calc(i uint32) (idx, pos uint32) {

	idx = i >> 3 //相当于i / 8,即字节位置
	if idx >= bitmap.ArraySize {
		panic("数组越界.")
		return
	}
	pos = i % BitSize //位位置
	return
}

//ByteToBinaryString函数来源:
// Go语言版byte变量的二进制字符串表示
// http://www.sharejs.com/codes/go/4357
func ByteToBinaryString(data byte) (str string) {
	var a byte
	for i := 0; i < 8; i++ {
		a = data
		data <<= 1
		data >>= 1

		switch a {
		case data:
			str += "0"
		default:
			str += "1"
		}

		data <<= 1
	}
	return str
}
运行结果:

  

数组大小: 3
set()  value= 5  idx= 0  pos= 5 00100000
set()  value= 4  idx= 0  pos= 4 00110000
set()  value= 2  idx= 0  pos= 2 00110100
set()  value= 1  idx= 0  pos= 1 00110110
set()  value= 3  idx= 0  pos= 3 00111110
set()  value= 17  idx= 2  pos= 1 00000010
set()  value= 13  idx= 1  pos= 5 00100000
排序后:
1 2 3 4 5 13 17

MAIL:  xcl_168@aliyun.com

BLOG: http://blog.csdn.net./xcl168




有疑问加站长微信联系(非本文作者)

本文来自:CSDN博客

感谢作者:xcltapestry

查看原文:Go语言实现位图排序(bitmap)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

4266 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传