lib/standard/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 import math
  22 import file
  23
  24 in "C header" `{
  25         #include <assert.h>
  26 `}
  27
  28 # Add support of binary operations related
  29 # to binary level of Integer
  30 # For compatibility reasons, xor, and, or methods
  31 # are still in the math.nit module
  32 redef class Int
  33
  34         # Sets the i-bit of self to the given value
  35         #     assert 11.setbit(0, 0) == 10
  36         #     assert 10.setbit(0, 1) == 11
  37         fun setbit(index: Int, value: Int): Int `{
  38                 assert(index >= 0 && index < 32);
  39
  40                 if(value == 1)
  41                         return recv | (1 << index);
  42                 else
  43                         return recv & ~(1 << index);
  44         `}
  45
  46         # Returns the i-bit value of self Integer
  47         #     assert 10.getbit(0) == 0
  48         #     assert 10.getbit(3) == 1
  49         fun getbit(index: Int): Int `{
  50                 assert(index >= 0 && index < 32);
  51
  52                 int op = 1 << index;
  53
  54                 if((recv & op) == 0)
  55                         return 0;
  56                 else
  57                         return 1;
  58         `}
  59
  60         # Give a binary representation of self Integer
  61         fun bits : Array[Int]
  62         do
  63                 var bits = new Array[Int].with_capacity(32)
  64
  65                 for i in [0..32[
  66                 do
  67                         bits[i] = getbit(i)
  68                 end
  69
  70                 return bits
  71         end
  72
  73         # Returns the number of bits of specified value (0 or 1)
  74         # in self
  75         #     assert 10.number_bits(1) == 2
  76         #     assert 10.number_bits(0) == 30
  77         fun number_bits(value: Int): Int `{
  78                 assert(value == 0 || value == 1);
  79
  80                 long int bound = 1L << 31;
  81                 int count = 0;
  82                 long int i;
  83
  84                 if(value == 1)
  85                 {
  86                         for(i=bound; i>0; i/=2)
  87                         {
  88                                 if(recv & i)
  89                                         count++;
  90                         }
  91                 }
  92                 else
  93                 {
  94                         for(i=bound; i>0; i/=2)
  95                         {
  96                                 if(!(recv & i))
  97                                         count++;
  98                         }
  99                 }
 100                 return count;
 101         `}
 102
 103         # Returns the position of the highest bit
 104         # set to 1 in self (the rightest bit is at position 0)
 105         #     assert 10.highest_bit == 3
 106         #     assert 1.highest_bit == 0
 107         fun highest_bit: Int `{
 108                 long int msb = 1L << 31;
 109                 int pos = 31;
 110
 111                 while(msb > 0 && !(recv & msb))
 112                 {
 113                         msb /= 2;
 114                         pos--;
 115                 }
 116
 117                 return pos;
 118         `}
 119 end