lib/core/bitset.nit

   1 # This file is part of NIT (http://www.nitlanguage.org).
   2 #
   3 # Copyright 2014 Julien Pagès <julien.pages@lirmm.fr>
   4 #
   5 # Licensed under the Apache License, Version 2.0 (the "License");
   6 # you may not use this file except in compliance with the License.
   7 # You may obtain a copy of the License at
   8 #
   9 #        http://www.apache.org/licenses/LICENSE-2.0
  10 #
  11 # Unless required by applicable law or agreed to in writing, software
  12 # distributed under the License is distributed on an "AS IS" BASIS,
  13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14 # See the License for the specific language governing permissions and
  15 # limitations under the License.
  16
  17 # Services to handle BitSet
  18 module bitset
  19
  20 import collection
  21 private import math
  22
  23 in "C header" `{
  24         #include <assert.h>
  25 `}
  26
  27 # Add support of binary operations related to binary level of Integer
  28 # For compatibility reasons, xor, and, or methods are still in the `math` module.
  29 redef class Int
  30
  31         # Sets the i-bit of self to the given `value`
  32         #
  33         #        assert 11.setbit(0, 0) == 10
  34         #        assert 10.setbit(0, 1) == 11
  35         fun setbit(index: Int, value: Int): Int `{
  36                 assert(index >= 0 && index < 32);
  37
  38                 if(value == 1)
  39                         return self | (1 << index);
  40                 else
  41                         return self & ~(1 << index);
  42         `}
  43
  44         # Returns the i-bit value of `self`
  45         #
  46         #        assert 10.getbit(0) == 0
  47         #        assert 10.getbit(3) == 1
  48         fun getbit(index: Int): Int `{
  49                 assert(index >= 0 && index < 32);
  50
  51                 int op = 1 << index;
  52
  53                 if((self & op) == 0)
  54                         return 0;
  55                 else
  56                         return 1;
  57         `}
  58
  59         # Give a binary representation of self Integer
  60         fun bits: Array[Int]
  61         do
  62                 var bits = new Array[Int].with_capacity(32)
  63
  64                 for i in [0..32[
  65                 do
  66                         bits[i] = getbit(i)
  67                 end
  68
  69                 return bits
  70         end
  71
  72         # Returns the number of bits of specified value (0 or 1) in `self`
  73         #
  74         #        assert 10.number_bits(1) == 2
  75         #        assert 10.number_bits(0) == 30
  76         fun number_bits(value: Int): Int `{
  77                 assert(value == 0 || value == 1);
  78
  79                 long int bound = 1L << 31;
  80                 int count = 0;
  81                 long int i;
  82
  83                 if(value == 1)
  84                 {
  85                         for(i=bound; i>0; i/=2)
  86                         {
  87                                 if(self & i)
  88                                         count++;
  89                         }
  90                 }
  91                 else
  92                 {
  93                         for(i=bound; i>0; i/=2)
  94                         {
  95                                 if(!(self & i))
  96                                         count++;
  97                         }
  98                 }
  99                 return count;
 100         `}
 101
 102         # Returns the position of the highest bit set to 1 in `self`
 103         #
 104         # The rightmost bit is at position 0.
 105         #
 106         #        assert 10.highest_bit == 3
 107         #        assert 1.highest_bit == 0
 108         fun highest_bit: Int `{
 109                 long int msb = 1L << 31;
 110                 int pos = 31;
 111
 112                 while(msb > 0 && !(self & msb))
 113                 {
 114                         msb /= 2;
 115                         pos--;
 116                 }
 117
 118                 return pos;
 119         `}
 120 end