BitOps


1   // Copyright (c) 1997  Per M.A. Bothner.
2   // This is free software;  for terms and warranty disclaimer see ./COPYING.
3   
4   package gnu.math;
5   
6   /** Implements logical (bit-wise) operations on infinite-precision integers.
7    * There are no BitOps object - all the functions here are static.
8    * The semantics used are the same as for Common Lisp.
9    * @author Per Bothner
10   */
11  
12  public class BitOps
13  {
14    private BitOps () { }
15  
16    /** Return the value of a specified bit in an IntNum. */
17    public static boolean bitValue (IntNum x, int bitno)
18    {
19      int i = x.ival;
20      if (x.words == null)
21        {
22      return bitno >= 32 ? i < 0 : ((i >> bitno) & 1) != 0;
23        }
24      else
25        {
26      int wordno = bitno >> 5;
27      return wordno >= i ? x.words[i-1] < 0
28        : (((x.words[wordno]) >> bitno) & 1) != 0;
29        }
30    }
31   
32    /** Return true iff an IntNum and an int have any true bits in common. */
33    public static boolean test (IntNum x, int y)
34    {
35      if (x.words == null)
36        return (x.ival & y) != 0;
37      return (y < 0) || (x.words[0] & y) != 0;
38    }
39  
40    /** Return true iff two IntNums have any true bits in common. */
41    public static boolean test (IntNum x, IntNum y)
42    {
43      if (y.words == null)
44        return test (x, y.ival);
45      else if (x.words == null)
46        return test (y, x.ival);
47      if (x.ival < y.ival)
48        {
49          IntNum temp = x;  x = y;  y = temp;
50        }
51      for (int i = 0;  i < y.ival;  i++)
52        {
53      if ((x.words[i] & y.words[i]) != 0)
54        return true;
55        }
56      return y.isNegative ();
57    }
58  
59    /** Return the logical (bit-wise) "and" of an IntNum and an int. */
60    public static IntNum and (IntNum x, int y)
61    {
62      if (x.words == null)
63        return IntNum.make (x.ival & y);
64      if (y >= 0)
65        return IntNum.make (x.words[0] & y);
66      int len = x.ival;
67      int[] words = new int[len];
68      words[0] = x.words[0] & y;
69      while (--len > 0)
70        words[len] = x.words[len];
71      return IntNum.make (words, x.ival);
72    }
73  
74    /** Return the logical (bit-wise) "and" of two IntNums. */
75    public static IntNum and (IntNum x, IntNum y)
76    {
77      if (y.words == null)
78        return and (x, y.ival);
79      else if (x.words == null)
80        return and (y, x.ival);
81      if (x.ival < y.ival)
82        {
83          IntNum temp = x;  x = y;  y = temp;
84        }
85      int i;
86      int len = y.isNegative () ? x.ival : y.ival;
87      int[] words = new int[len];
88      for (i = 0;  i < y.ival;  i++)
89        words[i] = x.words[i] & y.words[i];
90      for ( ; i < len;  i++)
91        words[i] = x.words[i];
92      return IntNum.make (words, len);
93    }
94  
95    /** Return the logical (bit-wise) "(inclusive) or" of two IntNums. */
96    public static IntNum ior (IntNum x, IntNum y)
97    {
98      return bitOp (7, x, y);
99    }
100 
101   /** Return the logical (bit-wise) "exclusive or" of two IntNums. */
102   public static IntNum xor (IntNum x, IntNum y)
103   {
104     return bitOp (6, x, y);
105   }
106 
107   /** Return the logical (bit-wise) negation of an IntNum. */
108   public static IntNum not (IntNum x)
109   {
110     return bitOp (12, x, IntNum.zero ());
111   }
112 
113   /** Return the boolean opcode (for bitOp) for swapped operands.
114    * I.e. bitOp (swappedOp(op), x, y) == bitOp (op, y, x).
115    */
116   public static int swappedOp (int op)
117   {
118     return
119     "\000\001\004\005\002\003\006\007\010\011\014\015\012\013\016\017"
120     .charAt (op);
121   }
122 
123   /** Do one the the 16 possible bit-wise operations of two IntNums. */
124   public static IntNum bitOp (int op, IntNum x, IntNum y)
125   {
126     switch (op)
127       {
128         case 0:  return IntNum.zero();
129         case 1:  return and (x, y);
130         case 3:  return x;
131         case 5:  return y;
132         case 15: return IntNum.minusOne();
133       }
134     IntNum result = new IntNum ();
135     setBitOp (result, op, x, y);
136     return result.canonicalize ();
137   }
138 
139   /** Do one the the 16 possible bit-wise operations of two IntNums. */
140   public static void setBitOp (IntNum result, int op, IntNum x, IntNum y)
141   {
142     if (y.words == null) ;
143     else if (x.words == null || x.ival < y.ival)
144       {
145     IntNum temp = x;  x = y;  y = temp;
146     op = swappedOp (op);
147       }
148     int xi;
149     int yi;
150     int xlen, ylen;
151     if (y.words == null)
152       {
153     yi = y.ival;
154     ylen = 1;
155       }
156     else
157       {
158     yi = y.words[0];
159     ylen = y.ival;
160       }
161     if (x.words == null)
162       {
163     xi = x.ival;
164     xlen = 1;
165       }
166     else
167       {
168     xi = x.words[0];
169     xlen = x.ival;
170       }
171     if (xlen > 1)
172       result.realloc (xlen);
173     int[] w = result.words;
174     int i = 0;
175     // Code for how to handle the remainder of x.
176     // 0:  Truncate to length of y.
177     // 1:  Copy rest of x.
178     // 2:  Invert rest of x.
179     int finish = 0;
180     int ni;
181     switch (op)
182       {
183       case 0:  // clr
184     ni = 0;
185     break;
186       case 1: // and
187     for (;;)
188       {
189         ni = xi & yi;
190         if (i+1 >= ylen) break;
191         w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
192       }
193     if (yi < 0) finish = 1;
194     break;
195       case 2: // andc2
196     for (;;)
197       {
198         ni = xi & ~yi;
199         if (i+1 >= ylen) break;
200         w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
201       }
202     if (yi >= 0) finish = 1;
203     break;
204       case 3:  // copy x
205     ni = xi;
206     finish = 1;  // Copy rest
207     break;
208       case 4: // andc1
209     for (;;)
210       {
211         ni = ~xi & yi;
212         if (i+1 >= ylen) break;
213         w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
214       }
215     if (yi < 0) finish = 2;
216     break;
217       case 5: // copy y
218     for (;;)
219       {
220         ni = yi;
221         if (i+1 >= ylen) break;
222         w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
223       }
224     break;
225       case 6:  // xor
226     for (;;)
227       {
228         ni = xi ^ yi;
229         if (i+1 >= ylen) break;
230         w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
231       }
232     finish = yi < 0 ? 2 : 1;
233     break;
234       case 7:  // ior
235     for (;;)
236       {
237         ni = xi | yi;
238         if (i+1 >= ylen) break;
239         w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
240       }
241     if (yi >= 0) finish = 1;
242     break;
243       case 8:  // nor
244     for (;;)
245       {
246         ni = ~(xi | yi);
247         if (i+1 >= ylen) break;
248         w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
249       }
250     if (yi >= 0)  finish = 2;
251     break;
252       case 9:  // eqv [exclusive nor]
253     for (;;)
254       {
255         ni = ~(xi ^ yi);
256         if (i+1 >= ylen) break;
257         w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
258       }
259     finish = yi >= 0 ? 2 : 1;
260     break;
261       case 10:  // c2
262     for (;;)
263       {
264         ni = ~yi;
265         if (i+1 >= ylen) break;
266         w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
267       }
268     break;
269       case 11:  // orc2
270     for (;;)
271       {
272         ni = xi | ~yi;
273         if (i+1 >= ylen) break;
274         w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
275       }
276     if (yi < 0)  finish = 1;
277     break;
278       case 12:  // c1
279     ni = ~xi;
280     finish = 2;
281     break;
282       case 13:  // orc1
283     for (;;)
284       {
285         ni = ~xi | yi;
286         if (i+1 >= ylen) break;
287         w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
288       }
289     if (yi >= 0) finish = 2;
290     break;
291       case 14:  // nand
292     for (;;)
293       {
294         ni = ~(xi & yi);
295         if (i+1 >= ylen) break;
296         w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
297       }
298     if (yi < 0) finish = 2;
299     break;
300       default:
301       case 15:  // set
302     ni = -1;
303     break;
304       }
305     // Here i==ylen-1; w[0]..w[i-1] have the correct result;
306     // and ni contains the correct result for w[i+1].
307     if (i+1 == xlen)
308       finish = 0;
309     switch (finish)
310       {
311       case 0:
312     if (i == 0 && w == null)
313       {
314         result.ival = ni;
315         return;
316       }
317     w[i++] = ni;
318     break;
319       case 1:  w[i] = ni;  while (++i < xlen)  w[i] = x.words[i];  break;
320       case 2:  w[i] = ni;  while (++i < xlen)  w[i] = ~x.words[i];  break;
321       }
322     result.ival = i;
323   }
324 
325   /** Extract a bit-field as an unsigned integer. */
326   public static IntNum extract (IntNum x, int startBit, int endBit)
327   {
328     //System.err.print("extract([");  if (x.words!=null) MPN.dprint(x.words);
329     //System.err.println (","+x.ival+"], start:"+startBit+", end:"+endBit);
330     if (endBit < 32)
331       {
332     int word0 = x.words == null ? x.ival : x.words[0];
333     return IntNum.make ((word0 & ~((-1) << endBit)) >> startBit);
334       }
335     int x_len;
336     if (x.words == null)
337       {
338     if (x.ival >= 0)
339       return IntNum.make (startBit >= 31 ? 0 : (x.ival >> startBit));
340     x_len = 1;
341       }
342     else
343       x_len = x.ival;
344     boolean neg = x.isNegative ();
345     if (endBit > 32 * x_len)
346       {
347     endBit = 32 * x_len;
348     if (!neg && startBit == 0)
349       return x;
350       }
351     else
352       x_len = (endBit + 31) >> 5;
353     int length = endBit - startBit;
354     if (length < 64)
355       {
356     long l;
357     if (x.words == null)
358       l = x.ival >> (startBit >= 32 ? 31 : startBit);
359     else
360       l = MPN.rshift_long (x.words, x_len, startBit);
361     return IntNum.make (l & ~((-1L) << length));
362       }
363     int startWord = startBit >> 5;
364     // Allocate a work buffer, which has to be large enough for the result
365     // AND large enough for all words we use from x (including possible
366     // partial words at both ends).
367     int buf_len = (endBit >> 5) + 1 - startWord;
368     int[] buf = new int[buf_len];
369     if (x.words == null)  // x < 0.
370       buf[0] = startBit >= 32 ? -1 : (x.ival >> startBit);
371     else
372       {
373     x_len -= startWord;
374     startBit &= 31;
375     MPN.rshift0 (buf, x.words, startWord, x_len, startBit);
376       }
377     x_len = length >> 5;
378     buf[x_len] &= ~((-1) << length);
379     return IntNum.make (buf, x_len + 1);
380   }
381 
382   // bit4count[I] is number of '1' bits in I.
383   static final byte[] bit4_count = { 0, 1, 1, 2,  1, 2, 2, 3,
384                      1, 2, 2, 3,  2, 3, 3, 4};
385 
386   public static int bitCount (int i)
387   {
388     int count = 0;
389     while (i != 0)
390       {
391     count += bit4_count[i & 15];
392     i >>>= 4;
393       }
394     return count;
395   }
396 
397   public static int bitCount (int[] x, int len)
398   {
399     int count = 0;
400     while (--len >= 0)
401       count += bitCount (x[len]);
402     return count;
403   }
404 
405   /** Count one bits in an IntNum.
406    * If argument is negative, count zero bits instead. */
407   public static int bitCount (IntNum x)
408   {
409     int i, x_len;
410     int[] x_words = x.words;
411     if (x_words == null)
412       {
413     x_len = 1;
414     i = bitCount (x.ival);
415       }
416     else
417       {
418     x_len = x.ival;
419     i = bitCount (x_words, x_len);
420       }
421     return x.isNegative () ? x_len * 32 - i : i;
422   }
423 }
424
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags