simple bitset?

[Will Fitzgerald]

I'm just starting up in my use of go, and I wonder if there would be any interest in small libraries for bitsets and perhaps bloom filters.

The bitset library I wrote is small (just five functions), but it might prove useful. 

In fact, I'd be glad for comments. Here's just the package:

https://gist.github.com/965762

[peterGo]

Will,

func MakeBitSet(max_size uint) bitset {
return make(bitset, (max_size+(64-1))/64)
}

Peter

[Will Fitzgerald]

That's sweet Peter.

Also,  arrays/slices of uints guaranteed to be initialized to 0? I did a quick check of the documentation, but didn't see this addressed. 

[peterGo]

Will,

The memory is initialized as described in the section on initial
values (§The zero value).

Making slices, maps and channels
http://golang.org/doc/go_spec.html#Making_slices_maps_and_channels

The zero value
http://golang.org/doc/go_spec.html#The_zero_value

Peter

On May 10, 10:22 pm, Will Fitzgerald <will.fitzger...@gmail.com>
wrote:

[zhai]

cute

func (set bitset) ClearBit( i uint) {

set[i/64]&^=1<<(i%64)

}

[Will Fitzgerald]

Wow.

Thanks for the excellent and immediate feedback.

I've placed the revised package and test code on GitHub:

https://github.com/willf/bitset

Will

[peterGo]

Will,

I don't see zhai's improved version of ClearBit in your revised bitset
package.

func (set bitset) ClearBit(i uint) {
set[i/64] &^= 1 << (i % 64)
}

Go has a &^ -- bit clear (and not) -- operator with a corresponding
&^= assignment operator.

Arithmetic operators
http://golang.org/doc/go_spec.html#Arithmetic_operators

Assignments
http://golang.org/doc/go_spec.html#Assignments

Peter

On May 10, 11:37 pm, Will Fitzgerald <will.fitzger...@gmail.com>
wrote:

[peterGo]

Will,

You expose the details of the implementation of the BitSet data
structure and allow direct read and write access.

If arguments are invalid, you allow the runtime to panic.

Here's an example of a more abstract and defensive approach.

package bitset

type BitSet struct {
bits uint
set []uint64
}

func New(bits uint) *BitSet {
return &BitSet{bits, make([]uint64, (bits+(64-1))/64)}
}

func (b *BitSet) Bit(i uint) bool {
if b != nil && i < b.bits {
return ((b.set[i/64] & (1 << (i % 64))) != 0)
}
return false
}

func (b *BitSet) SetBit(i uint) {
if b != nil && i < b.bits {
b.set[i/64] |= (1 << (i % 64))
}
}

func (b *BitSet) ClearBit(i uint) {
if b != nil && i < b.bits {
b.set[i/64] &^= 1 << (i % 64)
}
}

func (b *BitSet) Clear() {
if b != nil {
for i, _ := range b.set {
b.set[i] = 0

}
}
}

Peter

On May 10, 11:37 pm, Will Fitzgerald <will.fitzger...@gmail.com>
wrote:

[Will Fitzgerald]

I grow wiser every day. I had thought to make this a struct type, but decided against it for no good reason. 

Peter: Do you think it's a good idea to not panic on the out-of-bounds conditions in Bit/SetBit/ClearBit ? 

Will

[Will Fitzgerald]

Ok, I've made the changes recommended by  Peter and Zhai (and an anonymous commenter on the GitHub gist).

Here's the repo address again: https://github.com/willf/bitset

So, what other methods do you want?

Will

[roger peppe]

FWIW, i preferred the form of the original implementation. holding
max_size as a separate field is unnecessary because it's
implicit in the length of the slice.

it strikes me that bitset operations are very similar to operations
on large integers. you could actually use big.Int as an underlying
implementation. the only problem being that big.Int makes it quite
inefficient to twiddle numbered bits (each operation involves at least
one allocation).

if SetBit and Bit methods were added to big.Int, perhaps there would be no
need for a separate bitset package.

package bits
import "big"

type Bits big.Int

var zero = new(big.Int)

func mask(n int) *big.Int {
m := big.NewInt(1)
return m.Lsh(m, uint(n))
}

func (b *Bits) Get(i int) bool {
n := (*big.Int)(b)
m := mask(i)
return zero.Cmp(m.And(n, m)) == 0
}

func (b *Bits) Set(i int) {
n := (*big.Int)(b)
n.Or(n, mask(i))
}

func (b0 *Bits) Union(b1 *Bits) {
n0 := (*big.Int)(b0)
n0.Or(n0, (*big.Int)(b1))

[peterGo]

Roger,

On May 11, 8:48 am, roger peppe <rogpe...@gmail.com> wrote:
> FWIW, i preferred the form of the original implementation. holding
> max_size as a separate field is unnecessary because it's
> implicit in the length of the slice.

The length of the slice gives the number of uint64s allocated, which,
multiplied by 64, is not the same as the number of bits in the bit
set. For example, bitset.New(42).

Peter

[roger peppe]

On 11 May 2011 14:12, peterGo <go.pe...@gmail.com> wrote:
> Roger,
>
> On May 11, 8:48 am, roger peppe <rogpe...@gmail.com> wrote:
>> FWIW, i preferred the form of the original implementation. holding
>> max_size as a separate field is unnecessary because it's
>> implicit in the length of the slice.
>
> The length of the slice gives the number of uint64s allocated, which,
> multiplied by 64, is not the same as the number of bits in the bit
> set. For example, bitset.New(42).

yes, but does it matter if the bitset is a little bit larger than requested?

[Will Fitzgerald]

I think it does matter -- that is, it matters when the set/get/clear calls are "out of bounds."  It's not the wasted bits, but the semantics.

I still wonder if the methods should panic on out of bounds.

Also, I've added a Size() method

https://github.com/willf/bitset

Will

[Ryanne Dolan]

It should panic. There is no good reason for a package to avoid panicking when the programmer uses the package wrong. However, you don't want packages panicking in unpredictable ways, e.g. when a file can't be opened etc.

Ryanne

[zhai]

Also, I've added a Size() method

so,it has MaxSize() and Size()

How about rename the MaxSize() to Cap(), just alike built-in function cap()

and rename the Size() to Count(), because it's count the "1" in BitSet.

[Will Fitzgerald]

Zhai,

Good idea. And done.

 Is Count()  a standard method name? That is, might be used for other set-like things?

https://github.com/willf/bitset

Will

[Michael Jones]

Frequently in bit strings there is a desire for the four functions:

find {first|last}{one|zero}

which your implementation can magically do faster than the user by looking for 64-bits of zero or ones while iterating. which end is first is up to you. Hardware manufacturers have implemented every permutation over the years. Since you are abstracted from the HW and since you have an index, then maybe first could be up from index zero (first == lowest) and last could be down from end (last = highest).

--

Michael T. Jones

   Chief Technology Advocate, Google Inc.

   1600 Amphitheatre Parkway, Mountain View, California 94043

   Email: m...@google.com  Mobile: 650-335-5765  Fax: 650-649-1938

   Organizing the world's information to make it universally accessible and useful

[zhai]

replace  "i / 64" with "i >>6"

before:

--- prog list "MakeBitSet" ---

0000 (k.go:32) TEXT    MakeBitSet+0(SB),$80-16

0001 (k.go:33) MOVL    max_size+0(FP),AX

0002 (k.go:33) ADDL    $63,AX

0003 (k.go:33) MOVL    $64,BX

0004 (k.go:33) MOVL    $0,DX

0005 (k.go:33) DIVL    BX,            

after:

--- prog list "MakeBitSet" ---

0000 (k.go:32) TEXT    MakeBitSet+0(SB),$68-16

0001 (k.go:33) MOVL    max_size+0(FP),BX

0002 (k.go:33) ADDL    $63,BX

0003 (k.go:33) SHRL    $6,BX

0004 (k.go:33) MOVL    BX,DX

[Will Fitzgerald]

Yes! 

Done.

[Fango]

Just FYI, here's something similar

http://groups.google.com/group/golang-nuts/msg/6ba92da45c45fce0

[roger peppe]

here's one i did in another language (related to Go) some
time ago. perhaps its most significant feature is the
approach to set operations (the X method).

it also allows "negative" sets, which are a useful generalisation.

http://code.google.com/p/inferno-os/source/browse/appl/lib/sets.b

[peterGo]

Roger,

If we use len(set)*64 instead of bits, it can cause problems. We
should abide by the contract made by bitset.New(bits).

Using set []uint64 and len(set)*64 for New(32), Bit(SetBit(64)) is
true. Later we change the internal implementation to set []uint32.
Now, using set []uint32 and len(set)*32 for New(32), Bit(SetBit(64))
is false or a panic.

Peter

On May 11, 9:16 am, roger peppe <rogpe...@gmail.com> wrote:

[zhai]

On Wed, May 11, 2011 at 10:32 PM, Michael Jones <m...@google.com> wrote:

Frequently in bit strings there is a desire for the four functions:

find {first|last}{one|zero}

 

FYI:

 

Intel® 64 and IA-32 Architectures

Software Developer’s Manual

Volume 2A:

Instruction Set Reference, A-M

BSF—Bit Scan Forward

BSR—Bit Scan Revers

BTC—Bit Test and Complement

BTS—Bit Test and Set

BTR—Bit Test and Reset

[roger peppe]

On 11 May 2011 16:17, peterGo <go.pe...@gmail.com> wrote:
> Roger,
>
> If we use len(set)*64 instead of bits, it can cause problems. We
> should abide by the contract made by bitset.New(bits).
>
> Using set []uint64 and len(set)*64 for New(32), Bit(SetBit(64)) is
> true. Later we change the internal implementation to set []uint32.
> Now, using set []uint32 and len(set)*32 for New(32), Bit(SetBit(64))
> is false or a panic.

if you document that getting or setting a bit beyond the
limit gives rise to undefined behaviour, then it doesn't matter.

personally, i think if you're going to use a slice, you might
as well make the set arbitrary size and extend the slice
as necessary.

[peterGo]

Will,

On May 11, 9:26 am, Will Fitzgerald <will.fitzger...@gmail.com> wrote:
> I think it does matter -- that is, it matters when the set/get/clear calls
> are "out of bounds." It's not the wasted bits, but the semantics.

Exactly. The function semantics must be well-defined. For example,
even though this shift is out-of-bounds, it doesn't panic and it's
behavior is well-defined.

package main

import (
"fmt"
)

func main() {
u := uint64(1)
s := u << 1024
fmt.Println(u, s)
}

"The shift count must be 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."
http://golang.org/doc/go_spec.html#Arithmetic_operators

Also, for another example,

Integer overflow
http://golang.org/doc/go_spec.html#Integer_overflow

Peter

[Fango]

This might be slightly simpler.
http://code.google.com/p/inferno-os/source/browse/appl/lib/sets32.b

I like their *completeness*

Cheers,
Fango

On May 11, 11:00 pm, roger peppe <rogpe...@gmail.com> wrote:
> here's one i did in another language (related to Go) some
> time ago. perhaps its most significant feature is the
> approach to set operations (the X method).
>
> it also allows "negative" sets, which are a useful generalisation.
>
> http://code.google.com/p/inferno-os/source/browse/appl/lib/sets.b
>

[Will Fitzgerald]

I think that the capacity should be checked on get/set/clear, and should panic on excess. 

Also, I think that checking for a null reference is unnecessary, since the same panicking should be done if checked. But I think it's fine to Clear and Count a null reference, I guess.

Changes made, with some more unit tests during my pm break...back to regular work.

https://github.com/willf/bitset 

[peterGo]

Will,

> Changes made, with some more unit tests during my pm break...back to regular
> work.
>
> https://github.com/willf/bitset

Here's some more improvements to consider.

When you changed /64 to >>6, you missed one! Revised version:

func New(capacity uint) *BitSet {
return &BitSet{capacity, make([]uint64, (capacity+(64-1))>>6)}
}

As an analog to >> for integer division by powers of 2, consider & for
integer remainder after division by powers of 2.

Change all "(i % 64)" to "(i & (64-1))". For example,

func (b *BitSet) Bit(i uint) bool {

if i >= b.capacity {
panic(fmt.Sprintf("index out of range: %v", i))
}
return ((b.set[i>>6] & (1 << (i & (64-1)))) != 0)
}

If the compiler doesn't optimize for powers of 2, we go from

MOVL AX,autotmp_0003+-8(SP)

MOVL DX,autotmp_0004+-12(SP)

MOVL i+0(FP),BP

MOVL BP,autotmp_0005+-16(SP)

MOVL $64,autotmp_0006+-20(SP)

MOVL autotmp_0006+-20(SP),CX

MOVL autotmp_0005+-16(SP),AX

MOVL $0,DX

DIVL CX,

MOVL DX,CX

MOVL autotmp_0004+-12(SP),DX

MOVL autotmp_0003+-8(SP),AX

to

MOVL i+0(FP),BP

MOVL BP,autotmp_0000+-8(SP)

MOVL autotmp_0000+-8(SP),CX

ANDL $63,CX


Peter

[Ryanne Dolan]

Agree.

Ryanne

[Will Fitzgerald]

Peter,

Again, thank you. The changes have been committed. 

https://github.com/willf/bitset

Will

[peterGo]

Will,

Revise the Count for-range loop,

func (b *BitSet) Count() uint {
if b != nil {
cnt := uint64(0)
for _, s := range b.set {
cnt += popcount_2(s)
}
return uint(cnt)
}
return 0
}

In this case, you want s not i. It usually helps to be precise about
what you want to do; the compiler can be smarter and generate better
code. For example, the compiler can safely omit the slice index bounds
check for s; it has to do a slice index bounds check if you write
b.set[i].

Also, revise the Clear for range clause to discard the unnecessary
blank identifier.

RangeClause = Expression [ "," Expression ] ( "=" | ":=" ) "range"
Expression .
"If the range expression is a channel, only one iteration variable is
permitted, otherwise there may be one or two. "
http://golang.org/doc/go_spec.html#For_statements

func (b *BitSet) Clear() {
if b != nil {

for i := range b.set {

b.set[i] = 0
}
}
}

Peter

[Will Fitzgerald]

Yes, of course.

Committed.

https://github.com/willf/bitset

Will

[peterGo]

Will,

Here are some improvements to bitset that you may want to consider.

By design, the bitset package hides the implementation data
structures. However, the bitset package API encourages users to think
of a BitSet as an array of bits.

"An array is a numbered sequence of elements of a single type, called
the element type. The number of elements is called the length and is
never negative."
http://golang.org/doc/go_spec.html#Array_types

Therefore, globally change capacity in bitset to length. For example

type BitSet struct {
length uint
set []uint64
}

func New(length uint) *BitSet {
return &BitSet{length, make([]uint64, (length+(64-1))>>6)}
}

Changing capacity in bitset to length fixes another problem.

For a of type A or *A where A is an array type, or for a of type S
where S is a slice type:
* x must be an integer value and 0 <= x < len(a)
* a[x] is the array element at index x and the type of a[x] is the
element type of A
* if the index x is out of range, a run-time panic occurs
http://golang.org/doc/go_spec.html#Indexes

Therefore, an out-of-bounds check should read: x >= len(a), so we
should say i >= b.length not i >= b.capacity. For example,

func (b *BitSet) Bit(i uint) bool {

if i >= b.length {

panic(fmt.Sprintf("index out of range: %v", i))
}
return ((b.set[i>>6] & (1 << (i & (64 - 1)))) != 0)
}

Users may want to know the BitSet "array" length for bounds checking
and other purposes; there should be a BitSet Len method. For example,

func (b *BitSet) Len() uint {
return b.length
}

"The capacity of a slice is the number of elements for which there is
space allocated in the underlying array. At any time the following
relationship holds: 0 <= len(s) <= cap(s)"
http://golang.org/doc/go_spec.html#Length_and_capacity

For symmetry with slices, arrays have a len method and a nominal cap
method; by definition, cap(a) == len(a).

len(a) [n]T, *[n]T array length (== n)
cap(a) [n]T, *[n]T array length (== n)
http://golang.org/doc/go_spec.html#Length_and_capacity

For symmetry with arrays, it may be reasonable to provide a BitSet Cap
method. For example,

func (b *BitSet) Cap() uint {
// For an array a, cap(a) == len(a).
return b.length
}

Peter

[Michael Jones]

I had two nits that I held back from mentioning, but now so emboldened, here they are:

The internal routine popcount_2 might be better named popcount_uint64 so that the purpose, limits, etc. are clear to maintainers.

The ability to compare two such bitsets would be great: either Equal() for sameness or a signed comparison to signal (<, =, >). This is trivial but useful.

[Will Fitzgerald]

Thank you Peter -- I'll review these, I hope tomorrow.

Will

[Will Fitzgerald]

Michael,

Yes, we are not done. Equality will be easy, as you say. The find first & last set and unset bits methods have been asked for, too. We might want xor and friends.

Will

[zhai]

bitset_386.s

------------------------------------

//func BitScan(x uint32) int

//x must >0

TEXT bitset·bitscan(SB),7,$0

BSFL x+0(FP),AX

MOVL AX,r+4(FP)

RET

//func BitScanR(x uint32) int

//x must > 0

TEXT bitset·bitscanr(SB),7,$0

BSRL x+0(FP),AX

MOVL AX,r+4(FP)

RET

bitset.go

------------------------------------

package bitset

func bitscan(x uint32) uint

func bitscanr(x uint32) uint

type BitSet struct {

capacity uint

set      []uint32

}

func (b *BitSet) FindFirst() (index uint, found bool) {

var v uint32

for _, v = range b.set {

if v == 0 {

index += 32

} else {

break

}

}

if v != 0 {

// if v !=0 BitScan always return a positive index

index += uint(bitscan(v))

if index < b.capacity {

found = true

}

}

return

}

func (b *BitSet) FindLast() (index uint, found bool) {

var i uint

var ilen = uint(len(b.set))

var irem = ilen<<5 - b.capacity

b.set[ilen-1] <<= irem

b.set[ilen-1] >>= irem

for i = ilen - 1; i >= 0 && b.set[i] == 0; i-- {

}

if i >= 0 {

// if v !=0 BitScan always return a positive index

index = i<<5 + uint(bitscanr(b.set[i]))

found = true

}

return

}

func (b *BitSet) Clone() *BitSet {

c := New(b.capacity)

copy(c.set, b.set)

return c

}

func (b *BitSet) Copy(c *BitSet) (count uint) {

if c == nil {

return

}

copy(c.set, b.set)

count = c.capacity

if b.capacity < c.capacity {

count = b.capacity

}

return

}

//Copy start to end -1 to new bitset

func (b *BitSet) Sub(start, end uint) *BitSet {

if end <= start || end > b.capacity {

return nil

}

c := New(end - start)

if start&(32-1) == 0 {

copy(c.set, b.set[start>>32:(end+31)>>32])

return c

}

// the low  segment

ipos := start & (32 - 1)

ifirst := start >> 32

icount := end - start

ilen := icount >> 32

var i uint

for i = 0; i < ilen; i++ {

v := b.set[i+ifirst] >> ipos

c.set[i] = v | b.set[i+ifirst+1]<<(32-ipos)

}

if icount&(32-1) != 0 {

c.set[i] = b.set[i+ifirst] >> ipos

}

return c

}

[Will Fitzgerald]

Wow, Zhai ... I was just setting out to write these. 

Thanks!

WIll

[zhai]

func (b *BitSet) Equ(c *BitSet) bool {

if c == nil {

return false

}

if b.capacity != c.capacity {

return false

}

for p, v := range c.set {

if c.set[p] != v {

return false

}

}

return true

}

[zhai]

type BitSet struct {

capacity uint

set      []uint32

}

[Will Fitzgerald]

Zhai,

I'd be glad to write the unit tests, if you want to clone the git repository or do a fork and edit in place for the new code, as described at https://github.com/blog/844-forking-with-the-edit-button.

I actually don't know how to handle the assembly code.

Will

[zhai]

On Fri, May 13, 2011 at 10:39 AM, Will Fitzgerald <will.fi...@gmail.com> wrote:

Zhai,

I'd be glad to write the unit tests, if you want to clone the git repository or do a fork and edit in place for the new code, as described at https://github.com/blog/844-forking-with-the-edit-button.

I'll take a look 

[zhai]

func (b *BitSet) Sub(start, end uint) *BitSet {

ipos := start & (32 - 1)

ifirst := start >> 32

icount := end - start

ilen := icount >> 32

many bugs,please don't use it 

[Will Fitzgerald]

I added Len and Equ. (Zhai, there was a small typo in your Equ method, which new unit test caught).

https://github.com/willf/bitset

By the way, is Equ the standard method name for (naive) equality?

Will

[Will Fitzgerald]

It looks like Equal is used in the go package library:

~/projects/go/src/pkg $ egrep -r  "Equ" . | grep -v "_test" | grep 'func'

./asn1/asn1.go:func (oi ObjectIdentifier) Equal(other ObjectIdentifier) bool {

./bytes/bytes.go:func Equal(a, b []byte) bool {

./crypto/x509/x509.go:func (c *Certificate) Equal(other *Certificate) bool {

./net/ip.go:func (ip IP) Equal(x IP) bool {

./net/ip.go:func bytesEqual(x, y []byte) bool {

[Will Fitzgerald]

So, tentatively, I've renamed Equ to Equal

W

https://github.com/willf/bitset

[Canopée]

I have trouble understanding how you use http.Client when you want to
set a body and to define Headers.

I'm trying to make a simple SOAP request using SOAP. I tried using
Client.Do and Client.Post.

// with Do
func testSoap() {
httpClient := new (http.Client)
soapRequestContent := "<?xml version=\"1.0\" encoding=\"UTF-8\"
standalone=\"no\"?><SOAP-ENV:En ... elope>"
httpRequest, err := http.NewRequest("POST", "http://aSoapServer/",
strings.NewReader(soapRequestContent))
httpRequest.Header.Set("SOAPAction", "anAction")
httpRequest.Header.Set("Content-Type", "application/soap+xml;
charset=utf-8")
httpRequest.Header.Set("Content-Length", fmt.Sprintf("%d",
len(soapRequestContent)))
resp, err := httpClient.Do(httpRequest)
if err!=nil {
fmt.Println("Erreur : " + err.String())
}
r := bufio.NewReader(resp.Body)
line, err := r.ReadString('\n')
for err == nil {
fmt.Print(line)
line, err = r.ReadString('\n')
}
if err != os.EOF {
fmt.Println("Erreur lecture :")
fmt.Println(err)
}
resp.Body.Close()
fmt.Println();
}

With this method, my string (soapRequestContent) doesn't seem to be
posted as body of my request (there must be a bug in my code but I don't
see it).

// with Post
func testSoap() {
httpClient := new (http.Client)
soapRequestContent := "<?xml version=\"1.0\" encoding=\"UTF-8\"
standalone=\"no\"?><SOAP-ENV:En ... elope>"
resp, err := httpClient.Post("http://aSoapServer/",
"application/soap+xml; charset=utf-8",
strings.NewReader(soapRequestContent))
if err!=nil {
fmt.Println("Erreur : " + err.String())
}
r := bufio.NewReader(resp.Body)
line, err := r.ReadString('\n')
for err == nil {
fmt.Print(line)
line, err = r.ReadString('\n')
}
if err != os.EOF {
fmt.Println("Erreur lecture :")
fmt.Println(err)
}
resp.Body.Close()
fmt.Println();
}

With this method my body is correctly sent but I cannot specify the
SOAPAction header.

As I'm totally new to SOAP I may do something fundamentally wrong... Is
there somewhere an example of a simple SOAP interrogation in go ?

[Will Fitzgerald]

The following methods have been added:

Union (|), Intersection (&), Difference (^&), SymmetricDifference (^), and Subset

along with unit tests.

Thanks to Zhai for the somewhat tricky Subset code. (note to Zhai: some minor changes).

Comments welcome.

https://github.com/willf/bitset

[juha...@gmail.com]

Could you consider adding some convenience methods:

All() - returns true if all bits are set, false otherwise
Any() - returns true if any bit is set, false otherwise
None() - returns true if no bits are set, false otherwise

Flip(i) - flips bit on index i
FlipAll() - flips all bits

eg. c++ std bitset library has all these: http://www.cplusplus.com/reference/stl/bitset/

[Will Fitzgerald]

Yes, along with find first/last set/unset bits. Zhai's written these, but I haven't incorporated them yet.

[Will Fitzgerald]

I'm not quite sure I like the names, but I added, as suggested:

All() - returns true if all bits are set, false otherwise
Any() - returns true if any bit is set, false otherwise
None() - returns true if no bits are set, false otherwise

Flip(i) - flips bit on index i
FlipAll() - flips all bits

https://github.com/willf/bitset

[Michael Jones]

Compliment is the standard term for flip.

[chris dollin]

On 16 May 2011 15:05, Michael Jones <m...@google.com> wrote:
> Compliment is the standard term for flip.

Complement, surely?

Chris

--
Chris "why, yes, it is a trigger for me, how did you know?" Dollin

[ron minnich]

On Mon, May 16, 2011 at 7:12 AM, chris dollin <ehog....@googlemail.com> wrote:
> On 16 May 2011 15:05, Michael Jones <m...@google.com> wrote:
>> Compliment is the standard term for flip.
>
> Complement, surely?

Maybe. "That was the finest bit flip ever. I compliment you on your complement!"

ron

[chris dollin]

"Invert" has the appropriate meaning and is more compact ...

Chris

--
Chris "invirt, compect -- Clouseau?" Dollin

[John Asmuth]

Same with "flip".

[Will Fitzgerald]

I think there are a few separate issues.

1. What should the method be named that flips a particular bit in a BitSet?

I think Flip is fine. Invert would also be ok. 

2. Should there be a method that flips all the bits in a bit set, destructively?

I think so, and FlipAll or InvertAll are reasonable names.

3. Should there be a method which takes as input a BitSet and returns its complement?

I think so, and Complement is the right name. This hasn't been created yet. But it depends on the answer to this question:

4. In general, should there be destructive and non-destructive versions of the set operations (union/difference/intersection/symmetric difference, complement)?  

I'm not sure what I think about this. Perhaps you all could provide some wisdom.

Will

[roger peppe]

On 16 May 2011 15:39, Will Fitzgerald <will.fi...@gmail.com> wrote:
> 4. In general, should there be destructive and non-destructive versions of
> the set operations (union/difference/intersection/symmetric difference,
> complement)?

inspired by your package, i've created a CL that adds Bit and SetBit
methods to big.Int
(see http://codereview.appspot.com/4538053/)

this would mean that big.Int would provide most of the
functionality of the bitset package at similar runtime cost
(admittedly the methods would not be quite so obviously
named, Union->Or, Difference->AndNot, Intersection->And,
Symmetric Difference->Xor, etc).

big.Int provides destructive and non-destructive versions
of all its operations (through the use of 3-operand functions).

there are still some operations that will be slow using bit.Int,
bit counting being one, although it has the advantage of already
working with quite a few other parts of the standard Go library
(e.g. random number generation).

[Michael Jones]

thank you all for spelling correction. *blush*

[Will Fitzgerald]

I like this very much.

Have you done benchmarking on this, especially on setting (SetBit/ClearBit) and testing (Bit), and in comparison to this implementation? These are the cases I care about especially. 

Will

[Will Fitzgerald]

Here is the benchmarking I did. I compared using uint64, uint32, uint, and big.Int in random set/get loops:

bitset.BenchmarkSetBit64 50000000        69 ns/op

bitset.BenchmarkGetBit64 50000000        66 ns/op

bitset.BenchmarkSetBit32 50000000        62 ns/op

bitset.BenchmarkGetBit32 50000000        55 ns/op

bitset.BenchmarkSetBit 50000000        74 ns/op

bitset.BenchmarkGetBit 50000000        64 ns/op

bitset.BenchmarkSetBitBig 1000000      1733 ns/op

bitset.BenchmarkGetBitBig 50000000        70 ns/op

I used the most recent patch to get SetBit and Bit for bit.Int.

Here's the set loop benchmark I wrote. The other loops are similar. I've not used the big package before (or the rand pkg either), so please excuse the mess. Let me know if this seems wildly inappropriate. I assume the large increase using set is due to memory allocation.

func BenchmarkSetBitBig(b *testing.B) {

b.StopTimer()

r := rand.New(rand.NewSource(0))

sz := 100000

s := new(big.Int)

s.SetBit(s,sz-1,1)

b.StartTimer()

    for i := 0; i < b.N; i++ {

        s.SetBit(s, int(r.Int31n(int32(sz))),1)

    }

} 

[Kyle Lemons]

I don't know for a fact that any optimizations are done which would make overwriting a high with a 1 faster, but just to make sure, I would use i%2 instead of 1 in the SetBit.

--
~Kyle

"Everyone knows that debugging is twice as hard as writing a program in the first place. So if you're as clever as you can be when you write it, how will you ever debug it?" 
— Brian Kernighan

[robert....@mercadolibre.com]

Hi.

Not sure if this is the right place to ask, but I need a way to reverse the BitSet.

Currently the first stays on the right and grows toward the left, but I'm creating a package to handle ISO8583 messages and I need the fields to be identified from left to right.

Is this possible to do with bitset library?

Thank you.

[Egon]

On Thursday, 23 April 2015 21:36:52 UTC+3, robert....@mercadolibre.com wrote:

Hi.

Not sure if this is the right place to ask, but I need a way to reverse the BitSet.

Currently the first stays on the right and grows toward the left, but I'm creating a package to handle ISO8583 messages and I need the fields to be identified from left to right.

I suggest creating a new question instead and show an example of... this is what I have, and would like this to happen etc. Possibly a link to play.golang.org with code that uses that library.

The question, as is, doesn't make much sense to me. BitSet contains by definition is a set, which doesn't have any ordering.

You probably mean https://en.wikipedia.org/wiki/ISO_8583#Bitmaps?

(Create a new question with that information... it's easier to track a problem that way)

Is this possible to do with bitset library?

It's something that should be part of the iso8583 package, it doesn't make sense to use a separate library for it.

 

Thank you.

[Robert Barreiro]

Thanks Egon.

I am building an ISO8583 library, not using an existing one.

Regards,

Robert.

--

Robert Barreiro.

[Egon]

On Thursday, 23 April 2015 21:36:52 UTC+3, robert....@mercadolibre.com wrote:

Anyways... did you mean this https://play.golang.org/p/e5B5L4ER9z

 

Thank you.

[Egon]

Sorry, misunderstood the ordering https://play.golang.org/p/sycUxCZyxf

 

 

Thank you.

[Robert Barreiro]

Awesome! :-)

Very simple as I like.

Thanks Egon.

--

Robert Barreiro.

[Robert Barreiro]

Now it's perfect.

Give me your full name, the file will have your name on it (planning to "open source it" when its ready).

--

Robert Barreiro.

[Egon]

On Thursday, 23 April 2015 22:56:35 UTC+3, Robert Barreiro wrote:

Now it's perfect.

Give me your full name, the file will have your name on it (planning to "open source it" when its ready).

Egon Elbre... although usually it's preferable to have contributors in a separate file or readme - otherwise when there are improvements/changes to the actual file it will be crowed :)... try to keep the code clear of any noise - it'll be easier to read that way.

[Robert Barreiro]

Yes sure; will let you know when it's released.

Thanks for your help and advise.

Regards,

Robert.

--

Robert Barreiro.

[Dan Kortschak]

You need to wrap the shift in IsSet with parens to get the correct behaviour.

https://play.golang.org/p/oOe1Gd4C2G (cf orig https://play.golang.org/p/s5SiJqc5rG)

[Robert Barreiro]

You read my mind! I was just creating a dump function to return a string will all the bits on and off and I was getting all zeros.

Thanks Dan!

--

Robert Barreiro.