BitVector: Difference between revisions
From charlesreid1
(Created page with "quick example: Keeping track of a subset S of a large population of potential objects P, <math>S \subset P</math> If our problem conforms to the limitation that the size of...") |
No edit summary |
||
| Line 10: | Line 10: | ||
For example, let's suppose you were keeping track of 5 binary flags, or 32 values. Then we switch different flags, and end up with different values. That is, the binary number 11111 would become index 31 (the last index); 10110 becomes index 22; etc. | For example, let's suppose you were keeping track of 5 binary flags, or 32 values. Then we switch different flags, and end up with different values. That is, the binary number 11111 would become index 31 (the last index); 10110 becomes index 22; etc. | ||
Also see this video, about halfway through - Stanford Algorithms lecture: http://openclassroom.stanford.edu/MainFolder/VideoPage.php?course=IntroToAlgorithms&video=CS161L13P1&speed=100 | |||
Latest revision as of 04:51, 27 June 2017
quick example:
Keeping track of a subset S of a large population of potential objects P,
$ S \subset P $
If our problem conforms to the limitation that the size of S should be roughly the size of P, or that P is a reasonable size, then we can use a bit vector to represent this.
We create an array of booleans, and we represent all the potential Ps as a binary vector. Then each bit is turned on or off, which yields an integer number, which yields an array element.
For example, let's suppose you were keeping track of 5 binary flags, or 32 values. Then we switch different flags, and end up with different values. That is, the binary number 11111 would become index 31 (the last index); 10110 becomes index 22; etc.
Also see this video, about halfway through - Stanford Algorithms lecture: http://openclassroom.stanford.edu/MainFolder/VideoPage.php?course=IntroToAlgorithms&video=CS161L13P1&speed=100