📄 bitsets.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN"><!-- This collection of hypertext pages is Copyright 1995-2005 by Steve Summit. --><!-- Content from the book "C Programming FAQs: Frequently Asked Questions" --><!-- (Addison-Wesley, 1995, ISBN 0-201-84519-9) is made available here by --><!-- permission of the author and the publisher as a service to the community. --><!-- It is intended to complement the use of the published text --><!-- and is protected by international copyright laws. --><!-- The on-line content may be accessed freely for personal use --><!-- but may not be published or retransmitted without explicit permission. --><!-- --><!-- this page built Sat Dec 24 21:47:47 2005 by faqproc version 2.7 --><!-- from source file miscbits.sgml dated Wed Dec 21 13:02:12 2005 --><!-- corresponding to FAQ list version 4.0 --><html><!-- Mirrored from c-faq.com/misc/bitsets.html by HTTrack Website Copier/3.x [XR&CO'2008], Sat, 14 Mar 2009 07:59:04 GMT --><head><meta name=GENERATOR content="faqproc"><title>Question 20.8</title><link href="bitmanip.html" rev=precedes><link href="endiantest.html" rel=precedes><link href="index.html" rev=subdocument></head><body bgcolor="#ffffff"><a href="bitmanip.html" rev=precedes><img src="../images/buttonleft.gif" alt="prev"></a><a href="index.html" rev=subdocument><img src="../images/buttonup.gif" alt="up"></a><a href="endiantest.html" rel=precedes><img src="../images/buttonright.gif" alt="next"></a> <a href="../index-2.html"><img src="../images/buttontop.gif" alt="top/contents"></a><a href="../search.html"><img src="../images/buttonsrch.gif" alt="search"></a><hr><p><!-- qbegin --><h1>comp.lang.c FAQ list<font color=blue>·</font><!-- qtag -->Question 20.8</h1><p><font face=Helvetica size=8 color=blue><b>Q:</b></font>How can I implement sets or arrays of bits?</p><p><hr><p><font face=Helvetica size=8 color=blue><b>A:</b></font>Use arrays of <TT>char</TT> or <TT>int</TT>,with a few macros to access the desired bitin the proper cell of the array.Here are some simple macros to use with arrays of <TT>char</TT>:<pre>#include <limits.h> /* for CHAR_BIT */#define BITMASK(b) (1 << ((b) % CHAR_BIT))#define BITSLOT(b) ((b) / CHAR_BIT)#define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))#define BITCLEAR(a, b) ((a)[BITSLOT(b)] &= ~BITMASK(b))#define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))#define BITNSLOTS(nb) ((nb + CHAR_BIT - 1) / CHAR_BIT)</pre>(If you don't have <TT><limits.h></TT>,try using 8 for <TT>CHAR_BIT</TT>.)</p><p>Here are some usage examples.To declare an ``array'' of 47 bits:<pre> char bitarray[BITNSLOTS(47)];</pre>To set the23rdbit:<pre> BITSET(bitarray, 23);</pre>To test the35thbit:<pre> if(BITTEST(bitarray, 35)) ...</pre>Tocompute theunion of two bit arraysand place it in a third array(with all three arrays declared as above):<pre> for(i = 0; i < BITNSLOTS(47); i++) array3[i] = array1[i] | array2[i];</pre>To compute the intersection, use <TT>&</TT> instead of <TT>|</TT>.</p><p>As a more realistic example,here is a quick implementation of the Sieve of Eratosthenes,for computingprime numbers:<pre>#include <stdio.h>#include <string.h>#define MAX 10000int main(){ char bitarray[BITNSLOTS(MAX)]; int i, j; memset(bitarray, 0, BITNSLOTS(MAX)); for(i = 2; i < MAX; i++) { if(!BITTEST(bitarray, i)) { printf("%d\n", i); for(j = i + i; j < MAX; j += i) BITSET(bitarray, j); } } return 0;}</pre></p><p>See also question <a href="bitmanip.html">20.7</a>.</p><p>Additional links:<a href="bitsets.970425.html">further explanation</a></p><p>References:H&S Sec. 7.6.7 pp. 211-216<br></p><!-- aend --><p><hr><a href="bitmanip.html" rev=precedes><img src="../images/buttonleft.gif" alt="prev"></a><a href="index.html" rev=subdocument><img src="../images/buttonup.gif" alt="up"></a><a href="endiantest.html" rel=precedes><img src="../images/buttonright.gif" alt="next"></a> <a href="../questions.html"><img src="../images/buttontop.gif" alt="contents"></a><a href="../search.html"><img src="../images/buttonsrch.gif" alt="search"></a><br><!-- lastfooter --><a href="../about.html">about this FAQ list</a> <a href="../eskimo.html">about eskimo</a> <a href="../search.html">search</a> <a href="../feedback.html">feedback</a> <a href="copyright.html">copyright</a><p>Hosted by<a href="http://www.eskimo.com/"><img src="../../www.eskimo.com/img/link/eskitiny.gif" alt="Eskimo North"></a></body><!-- Mirrored from c-faq.com/misc/bitsets.html by HTTrack Website Copier/3.x [XR&CO'2008], Sat, 14 Mar 2009 07:59:04 GMT --></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -