C++ bitset

by admin on 2019年9月3日

Python 实现类似C++的bitset类

C++ 的 bitset 和 Java 的 BitSet
在位操作中都十分方便和强大,能够极大地节省内存,提高操作效率。遗憾的是,Python
竟然没有提供类似的类或模块。不过利用 Python
本身的强大能力,实现一个类似的 bitset
类,十分容易,下面我们就来纯手工打造一个属于自己的 Python 的 BitSet
类。本文抛砖引玉,在实际应用中,需要对异常进行处理,例如输入的位置不合法等。好了,不不多说,直接上实现代码

 

C++ bitset的实现教程,bitset实现教程

C++中bitset很方便的实现了位操作,有几点需要注意

它的模板是

00645   template<size_t _Nb>  
00646     class bitset  
00647     : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)>  

size_t
是在编译时候就已经得到了,然后将_Nb除上每个大小得到_Nw,_Nw即为模板泛化得到的首地址:

00077   template<size_t _Nw>  
00078     struct _Base_bitset  
00079     {  
00080       typedef unsigned long _WordT;  
00081   
00082       /// 0 is the least significant word.  
00083       _WordT        _M_w[_Nw];  

因此,bitset不需要像vector一样存一个首地址。

bitset的实现教程,bitset实现教程
C++中bitset很方便的实现了位操作,有几点需要注意 它的模板是 00645
templatesize_t _Nb 00646 class bitset 00647…

转载:

说明:bitset 就像 vector 一样,是
C++
的一个类模板库,用来对一个数的二进制位进行管理、判断等操作,使用时需要包含头文件
#include<bitset>。

#include<iostream>  
#include<bitset>  
using namespace std;  
void main()  
{  
bitset<4> bit(1110);   
cout<<bit.to_ulong()<<endl;   
bitset<5> ait(10001);  
cout<<ait.to_ulong()<<endl;  

}

Python的 BitSet 类实现

 

#!/usr/bin/env python
# -*- coding: utf-8 -*-
'''
Copyright (C)  2015 By Thomas Hu.  All rights reserved.

@author : Thomas Hu
@version: 1.0
@created: 2015-4-24
'''
import array

class BitSet(object):
    # from low to high "00000001 00000010 00000011", the array is [1, 2, 3]
    def __init__(self, capacity):
        #"B"类型相当于 C 语言的 unsigned char, 即占用1byte(8位),所以size大小设置为8
        self.unit_size = 8
        self.unit_count = int((capacity + self.unit_size - 1) / self.unit_size)
        self.capacity = capacity
        self.arr = array.array("B", [0] * self.unit_count)

    def any(self):
        #是否存在置为 1 的位
        for a in self.arr:
            if a != 0:
                return True
        return False

    def all(self):
        #是否所有位都为 1, 即是否存在置为 0 的位
        t = (1 << self.unit_size) - 1
        for a in self.arr:
            if (a & t) != t:
                return False
        return True


    def none(self):
        #是否所有位都为 0,即是否不存在置为 1 的位
        for a in self.arr:
            if a != 0:
                return False
        return True


    def count(self):
        #置为 1 的位的个数
        c = 0
        for a in self.arr:
            while a > 0:
                if a & 1:
                    c += 1
                a = a>>1
        return c


    def size(self):
        #所有位的个数
        return self.unit_count * self.unit_size

    def get(self, pos):
        #获取第 pos 位的值
        index = int(pos / self.unit_size)
        offset = (self.unit_size - (pos - index * self.unit_size) - 1) % self.unit_size
        return (self.arr[index] >> offset) & 1


    def test(self, pos):
        #判断第 pos 位的值是否为 1
        if self.get(pos):
            return True
        return False


    def set(self, pos=-1):
        #设置第 pos 位的值为 1,若 pos 为 -1, 则所有位都置为 1
        if pos >= 0:
            index = int(pos / self.unit_size)
            offset = (self.unit_size - (pos - index * self.unit_size) - 1) % self.unit_size
            self.arr[index] = (self.arr[index]) | (1 << offset)
        else:
            t = (1 << self.unit_size) - 1
            for i in range(self.unit_count):
                self.arr[i] = self.arr[i] | t


    def reset(self, pos=-1):
        #设置第 pos 位的值为 0,若 pos 为 -1, 则所有位都置为 0
        if pos >= 0:
            index = int(pos / self.unit_size)
            offset = (self.unit_size - (pos - index * self.unit_size) - 1) % self.unit_size
            x = (1 << offset)
            self.arr[index] = (self.arr[index]) & (~x)
        else:
            for i in range(self.unit_count):
                self.arr[i] = 0


    def flip(self, pos=-1):
        #把第 pos 位的值取反,若 pos 为 -1, 则所有位都取反
        if pos >= 0:
            if self.get(pos):
                self.reset(pos)
            else:
                self.set(pos)
        else:
            for i in range(self.unit_count):
                self.arr[i] = ~self.arr[i] + (1 << self.unit_size)

    def binstr(self):
        b = ""
        for a in self.arr:
            t = bin(a)
            b += "0" * (self.unit_size - len(t) + 2) + t + ","
        return "[" + b.replace("0b", "").strip(",") + "]"

    def show(self):
        return self.arr

def test():
    b = BitSet(20)
    print "size=", b.size()
    print "binstr=", b.binstr(), b.show()
    # Set first block test
    b.set(0)
    print "b.set(0), binstr=", b.binstr(), b.show()
    b.reset()
    b.set(1)
    print "b.set(1), binstr=", b.binstr(), b.show()

    # Set second block test
    b.reset()
    b.set(7)
    print "b.set(7), binstr=", b.binstr(), b.show()
    b.reset()
    b.set(8)
    print "b.set(8), binstr=", b.binstr(), b.show()
    b.reset()
    b.set(9)
    print "b.set(9), binstr=", b.binstr(), b.show()

    # any test
    print("\nany() test...")
    b.reset()
    print b.any(),
    b.set(0)
    print b.any(),
    b.set()
    print b.any()

    # all test
    print("\nall() test...")
    b.reset()
    print b.all(),
    b.set(0)
    print b.all(),
    b.set()
    print b.all()


    # none test
    print("\nnone() test...")
    b.reset()
    print b.none(),
    b.set(0)
    print b.none(),
    b.set()
    print b.none()


    print("\nflip() test...")
    b.reset()
    print b.binstr(),
    b.flip()
    print b.binstr()
    b.reset(1)
    print b.binstr(),
    b.flip()
    print b.binstr()




if __name__ == "__main__":
    test()

 

转载:

1.声明及定义

结果为什么是6和17啊
把十进制1110转化为2进制,用计算器算得为10001010110取后面四位,即为6
同理,把十进制的10001转为2进制得10011100010001,取后面五位,即为17

测试函数的输出结果

 

 

>>> 
size= 24
binstr= [00000000,00000000,00000000] array('B', [0, 0, 0])
b.set(0), binstr= [10000000,00000000,00000000] array('B', [128, 0, 0])
b.set(1), binstr= [01000000,00000000,00000000] array('B', [64, 0, 0])
b.set(7), binstr= [00000001,00000000,00000000] array('B', [1, 0, 0])
b.set(8), binstr= [00000000,10000000,00000000] array('B', [0, 128, 0])
b.set(9), binstr= [00000000,01000000,00000000] array('B', [0, 64, 0])

any() test...
False True True

all() test...
False False True

none() test...
True False False

flip() test...
[00000000,00000000,00000000] [11111111,11111111,11111111]
[10111111,11111111,11111111] [01000000,00000000,00000000]
>>> 

 

 

 

实现类似C++的bitset类 C++ 的 bitset 和
Java 的 BitSet
在位操作中都十分方便和强大,能够极大地节省内存,提高操作效率。遗憾的是,Py…

格式:bitset<N> var

其中 var 为 bitset 的类对象,N
表示该对象所占的位数,这里的位数指的是二进制。M 指的是 var
的初始值,可以是十六进制也可以是十进制,甚至还可以是 0-1 字符串。

  1     string str("11111");  2     bitset<10> a;  3     //将a初始化为000001010  4     bitset<10> e;  5     //将e的后8位初始化为1  6     bitset<10> f;  7     //将f的后5位初始化为1  8     bitset<10> d;  9     //无参数时每位都初始化为0

2.位操作成员函数

1.text

功能:测试 pos 为是否为1,是返回 1,不是返回 0。

2.any()

功能:测试所有位是否为 0 ,是返回0,不是返回1。

3.none()

功能:测试是否所有位为 0 ,是返回1,不是返回0.

4.count()

功能:统计位为 1 的个数并返回。

5.size()

功能:求取对象的大小并返回。

6.flip

功能:将 pos 为翻转,即 0-1 变换,当无参时,则翻转所有位。

7.set

功能:将 pos 位置 1,当无参时,将所有位置 1 。

8.reset

功能:将 pos 为置 0 ,当无参时则将所有位置 0 。

示例:

  1     bitset<10> a;  2     cout<<a<<endl;  3     cout<<a.test<<endl;  4     cout<<a.any()<<endl;  5     cout<<a.none()<<endl;  6     cout<<a.count()<<endl;  7     cout<<a.size()<<endl;  8     a.set();  9     cout<<a<<endl; 10     a.reset(); 11     cout<<a<<endl; 12     a.flip(); 13     cout<<a<<endl;

程序运行结果:

  1 0000001010  2 1  3 1  4 0  5 2  6 10  7 1111111111  8 0000000000  9 1111111111

值得注意的是:对某个对象的位可以像数组那样进行下标访问,并且还可以修改其
0-1 标志,如下修改对象的第 6 位并分别打印出各位:

  1     bitset<10> a;  2     a[5] = 1;  3     for(int i = 0;i<10;i++)  4         cout<<a[i]<<"";

3.转换成员函数

bitset
对一个数进行了二进制位的操作,即将某个数转换成了二进制形式,并对二进制的某些位进行了操作(还有
0-1
字符串),那么如果我们需要用到修改了某个二进制位的数时,则需要通过转换函数来实现。

1.to_ulong()

功能:将对象以 unsigned long
类型返回,若对象经过了位操作函数的修改,则返回修改后的值。

2.to_string()

功能:将对象以 0-1
字符串的形式返回,若对象经过了修改,则返回修改后的值。如下代码输出为:10
0000001010 。

  1     bitset<10> a;  2     int data = a.to_ulong();  3     string str = a.to_string();  4     cout<<data<<""<<str;

注意:bitset
对象只接受整型数据,如果初始化一个带有小数的数时,将自动截断,取整数部分进行操作。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图