Go language Bible - Chapter 6 methods - 6.5 example: bit array

Chapter 6 methods

Since the 1990s, object-oriented programming (OOP) has become a programming paradigm that dominates the engineering and educational circles. Therefore, almost all large-scale applied languages include OOP support, and Go language is no exception

In fact, OOP is not clearly defined, but the general meaning is that an object is actually a simple value or a variable. This object will contain some methods, while a method is a function associated with a special type. An object-oriented program will use methods to express its properties and corresponding operations, In this way, users who use this object do not need to operate the object directly, but do these things with the help of methods

In earlier chapters, we have actually used some methods provided by the standard library, such as the second method of time.Duration

const day = 24*time.Hour

In Section 2.5, we defined a method, a String method of Celsius type

func (c Celsius) String() string{
   return fmt.Sprintf("%g˚C",c)

In this chapter, the first aspect of OOP programming, we will show how to effectively define and use methods. We will cover the two key points of OOP programming, encapsulation and combination

6.5 example: bit array

Collections in Go language are generally represented in the form of map[T]bool, and T represents the element type. Although it is very flexible to use map to represent collection types, we still have a better form to represent them

For example, in the field of data flow analysis, the set element is usually a non negative integer, the set will contain many elements, and the set will often perform Union and intersection operations. In this case, bit array will perform better than map (for example, when we perform an http download task, we divide the file into many blocks according to a 16kb block. We need a global variable to identify which blocks have been downloaded. In this case, we also need to use the bit array.)

A bit array is usually represented by an unsigned number or slice called "word". Each bit of each element represents a value in the set. When bit i of the set is set, we are the set that contains element i

The following program shows a simple bit array type and uses three functions to operate it

type Insert struct {
   words []uint64
func (s *Insert) Has(x int) bool {
   word, bit := x/64,uint(x%64)
   return word < len(s.words) && s.words[word]&(1<<bit) !=0
func (s *Insert) Add(x int) {
   word,bit := x/64, uint(x%64)
   for word >= len(s.words){
      s.words = append(s.words,0)
   s.words[word] |= 1 << bit
func (s *Insert) UnionWith(t *Insert){
   for i, tword := range t.words {
      if i< len(s.words){
         s.words[i] |= tword
      }else {
         s.words = append(s.words,tword)

Because each word has 64 binary bits, in order to locate the bit bit of x, we use the quotient of x/64 as the subscript of the word, and the value obtained by x%64 as the position of the bit in the word. In the union with method, the logical "or" logical operation symbol of bit bit is used to complete the or calculation of 64 elements at one time

At present, this implementation lacks many necessary features. Let's add a method to implement it:

func (s *Insert) String() string{
   var buf bytes.Buffer
   for i,word := range s.words{
      if word == 0 {
      for j:=0;j<64;j++{
         if word&(1<<uint(j)) != 0 {
            if buf.Len()> len("{") {
               buf.WriteByte(' ')
   return buf.String()

Note that the String method is similar to the intsToString method in section 3.5.4. bytes.Buffer is often used in the String method. When you define a String method for a complex type, the fmt package will treat the value of this type specially, so that these types can look more friendly when printing, rather than directly printing their original values fmt will directly call the user-defined String method for the initial value. This mechanism depends on the interface and type assertion, which will be described in detail in Chapter 7

Now we can directly apply the IntSet defined above in actual combat

var x,y Insert
fmt.Println(x.String()) // {1 9 100}

fmt.Println(y.String()) // {9 42}

fmt.Println(x.String()) // {1 9 42 100}
fmt.Println(x.Has(9),x.Has(123)) // true false

It should be noted here that both String and Has methods use the pointer * Insert as the receiver, but in fact, it is not necessary to declare the receiver as a pointer type. However, when the other two functions operate on the s.words object, if the receiver is not declared as a pointer object, the actual operation is the copied object, not the original object. Therefore, the String side The method is defined on the IntSet pointer, so when our variable is InsSert type instead of IntSet pointer, the following unexpected situation may occur

fmt.Println(&x) // {1 9 42 100}
fmt.Println(x.String()) //{1 9 42 100}
fmt.Println(x) //{[4398046511618 68719476736]}

In the first Println, we print a * InSet pointer. This type of pointer does have a custom String method. In the second Println, we directly call the String () of the X variable Method. In this case, the compiler will implicitly insert the & operator before x, which is equivalent to calling the String method of the InSet pointer. In the third Println, because the InSet type has no method, Println will directly understand and print in the original way. In this case, the & symbol cannot be forgotten. In this scenario, we bind the String method to inse T object instead of the InSet pointer may be more appropriate, but this also requires specific analysis

Keywords: Go function

Added by ATLien on Fri, 12 Nov 2021 13:15:25 +0200