X hits on this document

1326 views

0 shares

0 downloads

0 comments

258 / 396

Chapter ‎18   Unsafe code

using System;

class BitArray { int[] bits; int length;

public BitArray(int length) { if (length < 0) throw new ArgumentException(); bits = new int[((length - 1) >> 5) + 1]; this.length = length; }

public int Length { get { return length; } }

public bool this[int index] { get { if (index < 0 || index >= length) { throw new IndexOutOfRangeException(); } return (bits[index >> 5] & 1 << index) != 0; } set { if (index < 0 || index >= length) { throw new IndexOutOfRangeException(); } if (value) { bits[index >> 5] |= 1 << index; } else { bits[index >> 5] &= ~(1 << index); } } } }

An instance of the BitArray class consumes substantially less memory than a corresponding bool[] (since each value of the former occupies only one bit instead of the latter’s one byte), but it permits the same operations as a bool[].

The following CountPrimes class uses a BitArray and the classical “sieve” algorithm to compute the number of primes between 1 and a given maximum:

class CountPrimes { static int Count(int max) { BitArray flags = new BitArray(max + 1); int count = 1; for (int i = 2; i <= max; i++) { if (!flags[i]) { for (int j = i * 2; j <= max; j += i) flags[j] = true; count++; } } return count; }

Copyright Microsoft Corporation 1999-2003. All Rights Reserved.245

Document info
Document views1326
Page views1326
Page last viewedSat Jan 21 16:56:53 UTC 2017
Pages396
Paragraphs9401
Words133190

Comments