CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Bit array - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy","wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"5222ed2f-c4da-4879-9e2f-f4ddf36b620b","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Bit_array","wgTitle":"Bit array","wgCurRevisionId":1279839196,"wgRevisionId":1279839196,"wgArticleId":1189937,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description matches Wikidata","Articles needing additional references from December 2010","All articles needing additional references","Webarchive template wayback links","Arrays","Bit data structures"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Bit_array","wgRelevantArticleId":1189937,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":20000,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q1992074","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false}; RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.pygments":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","ext.pygments.view","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.pygments%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.19"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Bit array - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Bit_array"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Bit_array&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Bit_array"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Bit_array rootpage-Bit_array skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" title="Main menu" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li><li id="n-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages"><span>Special pages</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Bit+array" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Bit+array" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Bit+array" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Bit+array" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Definition" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Definition"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Definition</span> </div> </a> <ul id="toc-Definition-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Basic_operations" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Basic_operations"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Basic operations</span> </div> </a> <ul id="toc-Basic_operations-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-More_complex_operations" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#More_complex_operations"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>More complex operations</span> </div> </a> <button aria-controls="toc-More_complex_operations-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle More complex operations subsection</span> </button> <ul id="toc-More_complex_operations-sublist" class="vector-toc-list"> <li id="toc-Population_/_Hamming_weight" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Population_/_Hamming_weight"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>Population / Hamming weight</span> </div> </a> <ul id="toc-Population_/_Hamming_weight-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Inversion" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Inversion"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.2</span> <span>Inversion</span> </div> </a> <ul id="toc-Inversion-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Find_first_one" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Find_first_one"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.3</span> <span>Find first one</span> </div> </a> <ul id="toc-Find_first_one-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Compression" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Compression"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Compression</span> </div> </a> <ul id="toc-Compression-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Advantages_and_disadvantages" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Advantages_and_disadvantages"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Advantages and disadvantages</span> </div> </a> <ul id="toc-Advantages_and_disadvantages-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Applications" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Applications"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Applications</span> </div> </a> <ul id="toc-Applications-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Examples" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Examples"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Examples</span> </div> </a> <ul id="toc-Examples-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Language_support" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Language_support"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>Language support</span> </div> </a> <ul id="toc-Language_support-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">10</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">11</span> <span>External links</span> </div> </a> <ul id="toc-External_links-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" title="Table of Contents" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Bit array</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 15 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-15" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">15 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D9%85%D8%B5%D9%81%D9%88%D9%81%D8%A9_%D8%A7%D9%84%D8%A8%D8%AA" title="مصفوفة البت – Arabic" lang="ar" hreflang="ar" data-title="مصفوفة البت" data-language-autonym="العربية" data-language-local-name="Arabic" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Bitkette" title="Bitkette – German" lang="de" hreflang="de" data-title="Bitkette" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-eo mw-list-item"><a href="https://eo.wikipedia.org/wiki/Bit%C4%89eno" title="Bitĉeno – Esperanto" lang="eo" hreflang="eo" data-title="Bitĉeno" data-language-autonym="Esperanto" data-language-local-name="Esperanto" class="interlanguage-link-target"><span>Esperanto</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%A2%D8%B1%D8%A7%DB%8C%D9%87_%D8%A8%DB%8C%D8%AA%DB%8C" title="آرایه بیتی – Persian" lang="fa" hreflang="fa" data-title="آرایه بیتی" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Tableau_de_bits" title="Tableau de bits – French" lang="fr" hreflang="fr" data-title="Tableau de bits" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Bit_array" title="Bit array – Italian" lang="it" hreflang="it" data-title="Bit array" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-hu mw-list-item"><a href="https://hu.wikipedia.org/wiki/Bitt%C3%B6mb" title="Bittömb – Hungarian" lang="hu" hreflang="hu" data-title="Bittömb" data-language-autonym="Magyar" data-language-local-name="Hungarian" class="interlanguage-link-target"><span>Magyar</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Bit_array" title="Bit array – Portuguese" lang="pt" hreflang="pt" data-title="Bit array" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%91%D0%B8%D1%82%D0%BE%D0%B2%D0%B0%D1%8F_%D0%BA%D0%B0%D1%80%D1%82%D0%B0" title="Битовая карта – Russian" lang="ru" hreflang="ru" data-title="Битовая карта" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/Bitski_niz" title="Bitski niz – Serbian" lang="sr" hreflang="sr" data-title="Bitski niz" data-language-autonym="Српски / srpski" data-language-local-name="Serbian" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-sh mw-list-item"><a href="https://sh.wikipedia.org/wiki/Bitski_niz" title="Bitski niz – Serbo-Croatian" lang="sh" hreflang="sh" data-title="Bitski niz" data-language-autonym="Srpskohrvatski / српскохрватски" data-language-local-name="Serbo-Croatian" class="interlanguage-link-target"><span>Srpskohrvatski / српскохрватски</span></a></li><li class="interlanguage-link interwiki-tl mw-list-item"><a href="https://tl.wikipedia.org/wiki/Bit_array" title="Bit array – Tagalog" lang="tl" hreflang="tl" data-title="Bit array" data-language-autonym="Tagalog" data-language-local-name="Tagalog" class="interlanguage-link-target"><span>Tagalog</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%91%D1%96%D1%82%D0%BE%D0%B2%D0%B0_%D0%BC%D0%B0%D0%BF%D0%B0" title="Бітова мапа – Ukrainian" lang="uk" hreflang="uk" data-title="Бітова мапа" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-zh-yue mw-list-item"><a href="https://zh-yue.wikipedia.org/wiki/%E4%BD%8D%E9%99%A3%E5%88%97" title="位陣列 – Cantonese" lang="yue" hreflang="yue" data-title="位陣列" data-language-autonym="粵語" data-language-local-name="Cantonese" class="interlanguage-link-target"><span>粵語</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E4%BD%8D%E6%95%B0%E7%BB%84" title="位数组 – Chinese" lang="zh" hreflang="zh" data-title="位数组" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1992074#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Bit_array" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Bit_array" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Bit_array"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Bit_array&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Bit_array&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Bit_array"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Bit_array&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Bit_array&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Bit_array" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Bit_array" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Bit_array&oldid=1279839196" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Bit_array&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Bit_array&id=1279839196&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FBit_array"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FBit_array"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Bit_array&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Bit_array&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1992074" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Array data structure that compactly stores bits</div> <style data-mw-deduplicate="TemplateStyles:r1251242444">.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}</style><table class="box-More_citations_needed plainlinks metadata ambox ambox-content ambox-Refimprove" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><a href="/wiki/File:Question_book-new.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/50px-Question_book-new.svg.png" decoding="async" width="50" height="39" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/75px-Question_book-new.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/100px-Question_book-new.svg.png 2x" data-file-width="512" data-file-height="399" /></a></span></div></td><td class="mbox-text"><div class="mbox-text-span">This article <b>needs additional citations for <a href="/wiki/Wikipedia:Verifiability" title="Wikipedia:Verifiability">verification</a></b>.<span class="hide-when-compact"> Please help <a href="/wiki/Special:EditPage/Bit_array" title="Special:EditPage/Bit array">improve this article</a> by <a href="/wiki/Help:Referencing_for_beginners" title="Help:Referencing for beginners">adding citations to reliable sources</a>. Unsourced material may be challenged and removed.<br /><small><span class="plainlinks"><i>Find sources:</i> <a rel="nofollow" class="external text" href="https://www.google.com/search?as_eq=wikipedia&q=%22Bit+array%22">"Bit array"</a> – <a rel="nofollow" class="external text" href="https://www.google.com/search?tbm=nws&q=%22Bit+array%22+-wikipedia&tbs=ar:1">news</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.google.com/search?&q=%22Bit+array%22&tbs=bkt:s&tbm=bks">newspapers</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.google.com/search?tbs=bks:1&q=%22Bit+array%22+-wikipedia">books</a> <b>·</b> <a rel="nofollow" class="external text" href="https://scholar.google.com/scholar?q=%22Bit+array%22">scholar</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.jstor.org/action/doBasicSearch?Query=%22Bit+array%22&acc=on&wc=on">JSTOR</a></span></small></span> <span class="date-container"><i>(<span class="date">December 2010</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <p>A <b>bit array</b> (also known as <b>bitmask</b>,<sup id="cite_ref-linux_1-0" class="reference"><a href="#cite_note-linux-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> <b>bit map</b>, <b>bit set</b>, <b>bit string</b>, or <b>bit vector</b>) is an <a href="/wiki/Array_data_structure" class="mw-redirect" title="Array data structure">array data structure</a> that compactly stores <a href="/wiki/Bit" title="Bit">bits</a>. It can be used to implement a simple <a href="/wiki/Set_data_structure" class="mw-redirect" title="Set data structure">set data structure</a>. A bit array is effective at exploiting <a href="/wiki/Bit-level_parallelism" title="Bit-level parallelism">bit-level parallelism</a> in hardware to perform operations quickly. A typical bit array stores <i>kw</i> bits, where <i>w</i> is the number of bits in the unit of storage, such as a <a href="/wiki/Byte" title="Byte">byte</a> or <a href="/wiki/Word_(computer_architecture)" title="Word (computer architecture)">word</a>, and <i>k</i> is some nonnegative integer. If <i>w</i> does not divide the number of bits to be stored, some space is wasted due to <a href="/wiki/Fragmentation_(computing)" title="Fragmentation (computing)">internal fragmentation</a>. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Bit_array&action=edit&section=1" title="Edit section: Definition"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A bit array is a mapping from some domain (almost always a range of integers) to values in the set {0, 1}. The values can be interpreted as dark/light, absent/present, locked/unlocked, valid/invalid, et cetera. The point is that there are only two possible values, so they can be stored in one bit. As with other arrays, the access to a single bit can be managed by applying an index to the array. Assuming its size (or length) to be <i>n</i> bits, the array can be used to specify a subset of the domain (e.g. {0, 1, 2, ..., <i>n</i>−1}), where a 1-bit indicates the presence and a 0-bit the absence of a number in the set. This set data structure uses about <i>n</i>/<i>w</i> words of space, where <i>w</i> is the number of bits in each <a href="/wiki/Word_(computer_architecture)" title="Word (computer architecture)">machine word</a>. Whether the least significant bit (of the word) or the most significant bit indicates the smallest-index number is largely irrelevant, but the former tends to be preferred (on <a href="/wiki/Endianness" title="Endianness">little-endian</a> machines). </p><p>A finite <a href="/wiki/Binary_relation" title="Binary relation">binary relation</a> may be represented by a bit array called a <a href="/wiki/Logical_matrix" title="Logical matrix">logical matrix</a>. In the <a href="/wiki/Calculus_of_relations" class="mw-redirect" title="Calculus of relations">calculus of relations</a>, these arrays are composed with <a href="/wiki/Matrix_multiplication" title="Matrix multiplication">matrix multiplication</a> where the arithmetic is Boolean, and such a composition represents <a href="/wiki/Composition_of_relations" title="Composition of relations">composition of relations</a>.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Basic_operations">Basic operations</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Bit_array&action=edit&section=2" title="Edit section: Basic operations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Although most machines are not able to address individual bits in memory, nor have instructions to manipulate single bits, each bit in a word can be singled out and manipulated using <a href="/wiki/Bitwise_operation" title="Bitwise operation">bitwise operations</a>. In particular: </p><p>Use <code>OR</code> to set a bit to one: </p> <pre> 11101<b>0</b>10 OR 00000<b>1</b>00 = 11101<b>1</b>10 </pre> <p><code>AND</code> to set a bit to zero: </p> <pre> 111010<b>1</b>0 AND 111111<b>0</b>1 = 111010<b>0</b>0 </pre> <p><code>AND</code> to determine if a bit is set, by zero-testing: </p> <pre> 1110101<b>0</b> 111010<b>1</b>0 AND 0000000<b>1</b> AND 000000<b>1</b>0 = 0000000<b>0</b> = 000000<b>1</b>0 (=0 ∴ bit isn't set) (≠0 ∴ bit is set) </pre> <p><code>XOR</code> to invert or toggle a bit: </p> <pre> 11101<b>0</b>10 11101<b>1</b>10 XOR 00000<b>1</b>00 XOR 00000<b>1</b>00 = 11101<b>1</b>10 = 11101<b>0</b>10 </pre> <p><code>NOT</code> to invert all bits: </p> <pre>NOT 10110010 = 01001101 </pre> <p>To obtain the <a href="/wiki/Mask_(computing)" title="Mask (computing)">bit mask</a> needed for these operations, we can use a <a href="/wiki/Bitwise_operation#Bit_shifts" title="Bitwise operation">bit shift</a> operator to shift the number 1 to the left by the appropriate number of places, as well as <a href="/wiki/Bitwise_negation" class="mw-redirect" title="Bitwise negation">bitwise negation</a> if necessary. </p><p>Given two bit arrays of the same size representing sets, we can compute their <a href="/wiki/Union_(set_theory)" title="Union (set theory)">union</a>, <a href="/wiki/Intersection_(set_theory)" title="Intersection (set theory)">intersection</a>, and <a href="/wiki/Complement_(set_theory)" title="Complement (set theory)">set-theoretic difference</a> using <i>n</i>/<i>w</i> simple bit operations each (2<i>n</i>/<i>w</i> for difference), as well as the <a href="/wiki/Signed_number_representations#Ones'_complement" title="Signed number representations">complement</a> of either: </p> <pre><b>for</b> i <b>from</b> 0 <b>to</b> n/w-1 complement_a[i] := <b>not</b> a[i] union[i]  := a[i] <b>or</b> b[i] intersection[i] := a[i] <b>and</b> b[i] difference[i]  := a[i] <b>and</b> (<b>not</b> b[i]) </pre> <p>If we wish to iterate through the bits of a bit array, we can do this efficiently using a doubly nested loop that loops through each word, one at a time. Only <i>n</i>/<i>w</i> memory accesses are required: </p> <pre><b>for</b> i <b>from</b> 0 to n/w-1 index := 0 // if needed word := a[i] <b>for</b> b <b>from</b> 0 to w-1 value := word <b>and</b> 1 ≠ 0 word := word shift right 1 // do something with value index := index + 1 // if needed </pre> <p>Both of these code samples exhibit ideal <a href="/wiki/Locality_of_reference" title="Locality of reference">locality of reference</a>, which will subsequently receive large performance boost from a data cache. If a cache line is <i>k</i> words, only about <i>n</i>/<i>wk</i> cache misses will occur. </p> <div class="mw-heading mw-heading2"><h2 id="More_complex_operations">More complex operations</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Bit_array&action=edit&section=3" title="Edit section: More complex operations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>As with <a href="/wiki/String_(computer_science)" title="String (computer science)">character strings</a> it is straightforward to define <i>length</i>, <i>substring</i>, <a href="/wiki/Lexicographical_order" class="mw-redirect" title="Lexicographical order">lexicographical</a> <i>compare</i>, <i>concatenation</i>, <i>reverse</i> operations. The implementation of some of these operations is sensitive to <a href="/wiki/Endianness" title="Endianness">endianness</a>. </p> <div class="mw-heading mw-heading3"><h3 id="Population_/_Hamming_weight"><span id="Population_.2F_Hamming_weight"></span>Population / Hamming weight</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Bit_array&action=edit&section=4" title="Edit section: Population / Hamming weight"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>If we wish to find the number of 1 bits in a bit array, sometimes called the population count or Hamming weight, there are efficient branch-free algorithms that can compute the number of bits in a word using a series of simple bit operations. We simply run such an algorithm on each word and keep a running total. Counting zeros is similar. See the <a href="/wiki/Hamming_weight" title="Hamming weight">Hamming weight</a> article for examples of an efficient implementation. </p> <div class="mw-heading mw-heading3"><h3 id="Inversion">Inversion</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Bit_array&action=edit&section=5" title="Edit section: Inversion"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Vertical flipping of a one-bit-per-pixel image, or some FFT algorithms, requires flipping the bits of individual words (so <code>b31 b30 ... b0</code> becomes <code>b0 ... b30 b31</code>). When this operation is not available on the processor, it's still possible to proceed by successive passes, in this example on 32 bits: </p> <div class="mw-highlight mw-highlight-lang-text mw-content-ltr" dir="ltr"><pre><span></span>exchange two 16-bit halfwords exchange bytes by pairs (0xddccbbaa -> 0xccddaabb) ... swap bits by pairs swap bits (b31 b30 ... b1 b0 -> b30 b31 ... b0 b1) The last operation can be written ((x&0x55555555) << 1) | (x&0xaaaaaaaa) >> 1)). </pre></div> <div class="mw-heading mw-heading3"><h3 id="Find_first_one">Find first one</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Bit_array&action=edit&section=6" title="Edit section: Find first one"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The <a href="/wiki/Find_first_set" title="Find first set">find first set</a> or <i>find first one</i> operation identifies the index or position of the 1-bit with the smallest index in an array, and has widespread hardware support (for arrays not larger than a word) and efficient algorithms for its computation. When a <a href="/wiki/Priority_queue" title="Priority queue">priority queue</a> is stored in a bit array, find first one can be used to identify the highest priority element in the queue. To expand a word-size <i>find first one</i> to longer arrays, one can find the first nonzero word and then run <i>find first one</i> on that word. The related operations <i>find first zero</i>, <i>count leading zeros</i>, <i>count leading ones</i>, <i>count trailing zeros</i>, <i>count trailing ones</i>, and <i>log base 2</i> (see <a href="/wiki/Find_first_set" title="Find first set">find first set</a>) can also be extended to a bit array in a straightforward manner. </p> <div class="mw-heading mw-heading2"><h2 id="Compression">Compression</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Bit_array&action=edit&section=7" title="Edit section: Compression"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A bit array is the most dense storage for "random" bits, that is, where each bit is equally likely to be 0 or 1, and each one is independent. But most data are not random, so it may be possible to store it more compactly. For example, the data of a typical fax image is not random and can be compressed. <a href="/wiki/Run-length_encoding" title="Run-length encoding">Run-length encoding</a> is commonly used to compress these long streams. However, most compressed data formats are not so easy to access randomly; also by compressing bit arrays too aggressively we run the risk of losing the benefits due to bit-level parallelism (<a href="/wiki/Array_programming" title="Array programming">vectorization</a>). Thus, instead of compressing bit arrays as streams of bits, we might compress them as streams of bytes or words (see <a href="/wiki/Bitmap_index#Compression" title="Bitmap index">Bitmap index (compression)</a>). </p> <div class="mw-heading mw-heading2"><h2 id="Advantages_and_disadvantages">Advantages and disadvantages</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Bit_array&action=edit&section=8" title="Edit section: Advantages and disadvantages"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Bit arrays, despite their simplicity, have a number of marked advantages over other data structures for the same problems: </p> <ul><li>They are extremely compact; no other data structures can store <i>n</i> independent pieces of data in <i>n</i>/<i>w</i> words.</li> <li>They allow small arrays of bits to be stored and manipulated in the register set for long periods of time with no memory accesses.</li> <li>Because of their ability to exploit bit-level parallelism, limit memory access, and maximally use the <a href="/wiki/Data_cache" class="mw-redirect" title="Data cache">data cache</a>, they often outperform many other data structures on practical data sets, even those that are more asymptotically efficient.</li></ul> <p>However, bit arrays are not the solution to everything. In particular: </p> <ul><li>Without compression, they are wasteful set data structures for sparse sets (those with few elements compared to their range) in both time and space. For such applications, compressed bit arrays, <a href="/wiki/Judy_array" title="Judy array">Judy arrays</a>, <a href="/wiki/Trie" title="Trie">tries</a>, or even <a href="/wiki/Bloom_filter" title="Bloom filter">Bloom filters</a> should be considered instead.</li> <li>Accessing individual elements can be expensive and difficult to express in some languages. If random access is more common than sequential and the array is relatively small, a byte array may be preferable on a machine with byte addressing. A word array, however, is probably not justified due to the huge space overhead and additional cache misses it causes, unless the machine only has word addressing.</li></ul> <div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Bit_array&action=edit&section=9" title="Edit section: Applications"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Because of their compactness, bit arrays have a number of applications in areas where space or efficiency is at a premium. Most commonly, they are used to represent a simple group of Boolean flags or an ordered sequence of Boolean values. </p><p>Bit arrays are used for <a href="/wiki/Priority_queue" title="Priority queue">priority queues</a>, where the bit at index <i>k</i> is set if and only if <i>k</i> is in the queue; this data structure is used, for example, by the <a href="/wiki/Linux_kernel" title="Linux kernel">Linux kernel</a>, and benefits strongly from a find-first-zero operation in hardware. </p><p>Bit arrays can be used for the allocation of <a href="/wiki/Page_(computing)" class="mw-redirect" title="Page (computing)">memory pages</a>, <a href="/wiki/Inode" title="Inode">inodes</a>, disk sectors, etc. In such cases, the term <i>bitmap</i> may be used. However, this term is frequently used to refer to <a href="/wiki/Raster_graphics" title="Raster graphics">raster images</a>, which may use multiple <a href="/wiki/Color_depth" title="Color depth">bits per pixel</a>. </p><p>Another application of bit arrays is the <a href="/wiki/Bloom_filter" title="Bloom filter">Bloom filter</a>, a probabilistic <a href="/wiki/Set_data_structure" class="mw-redirect" title="Set data structure">set data structure</a> that can store large sets in a small space in exchange for a small probability of error. It is also possible to build probabilistic <a href="/wiki/Hash_table" title="Hash table">hash tables</a> based on bit arrays that accept either false positives or false negatives. </p><p>Bit arrays and the operations on them are also important for constructing <a href="/wiki/Succinct_data_structure" title="Succinct data structure">succinct data structures</a>, which use close to the minimum possible space. In this context, operations like finding the <i>n</i>th 1 bit or counting the number of 1 bits up to a certain position become important. </p><p>Bit arrays are also a useful abstraction for examining streams of <a href="/wiki/Data_compression" title="Data compression">compressed</a> data, which often contain elements that occupy portions of bytes or are not byte-aligned. For example, the compressed <a href="/wiki/Huffman_coding" title="Huffman coding">Huffman coding</a> representation of a single 8-bit character can be anywhere from 1 to 255 bits long. </p><p>In <a href="/wiki/Information_retrieval" title="Information retrieval">information retrieval</a>, bit arrays are a good representation for the <a href="/w/index.php?title=Posting_list&action=edit&redlink=1" class="new" title="Posting list (page does not exist)">posting lists</a> of very frequent terms. If we compute the gaps between adjacent values in a list of strictly increasing integers and encode them using <a href="/wiki/Unary_coding" title="Unary coding">unary coding</a>, the result is a bit array with a 1 bit in the <i>n</i>th position if and only if <i>n</i> is in the list. The implied probability of a gap of <i>n</i> is 1/2<sup><i>n</i></sup>. This is also the special case of <a href="/wiki/Golomb_coding" title="Golomb coding">Golomb coding</a> where the parameter M is 1; this parameter is only normally selected when <span class="texhtml">−log(2 − <i>p</i>) / log(1 − <i>p</i>) ≤ 1</span>, or roughly the term occurs in at least 38% of documents. </p> <div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Bit_array&action=edit&section=10" title="Edit section: Examples"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div><p> Given a big file of <a href="/wiki/IPv4" title="IPv4">IPv4</a> addresses (more than 100 GB) — we need to count unique addresses. If we use generic <code>map[string]bool</code> — we will need more than 64 GB of <a href="/wiki/Random-access_memory" title="Random-access memory">RAM</a>, so lets use the <b>bit map</b>, in <a href="/wiki/Go_(programming_language)" title="Go (programming language)">Go</a>:</p><div class="mw-highlight mw-highlight-lang-go mw-content-ltr mw-highlight-lines" dir="ltr"><pre><span></span><span class="linenos" data-line="1"></span><span class="kn">package</span><span class="w"> </span><span class="nx">main</span> <span class="linenos" data-line="2"></span> <span class="linenos" data-line="3"></span><span class="kn">import</span><span class="w"> </span><span class="p">(</span> <span class="linenos" data-line="4"></span><span class="w"> </span><span class="s">"bufio"</span> <span class="linenos" data-line="5"></span><span class="w"> </span><span class="s">"fmt"</span> <span class="linenos" data-line="6"></span><span class="w"> </span><span class="s">"math/bits"</span> <span class="linenos" data-line="7"></span><span class="w"> </span><span class="s">"os"</span> <span class="linenos" data-line="8"></span><span class="p">)</span> <span class="linenos" data-line="9"></span> <span class="linenos" data-line="10"></span><span class="c1">// bitsetSize is the number of bytes needed for 2^32 bits (512 MiB)</span> <span class="linenos" data-line="11"></span><span class="kd">const</span><span class="w"> </span><span class="nx">bitsetSize</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">1</span><span class="w"> </span><span class="o"><<</span><span class="w"> </span><span class="mi">29</span> <span class="linenos" data-line="12"></span> <span class="linenos" data-line="13"></span><span class="kd">func</span><span class="w"> </span><span class="nx">main</span><span class="p">()</span><span class="w"> </span><span class="p">{</span> <span class="linenos" data-line="14"></span><span class="w"> </span><span class="nx">file</span><span class="p">,</span><span class="w"> </span><span class="nx">err</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nx">os</span><span class="p">.</span><span class="nx">Open</span><span class="p">(</span><span class="s">"ip_addresses"</span><span class="p">)</span> <span class="linenos" data-line="15"></span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="nx">err</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="kc">nil</span><span class="w"> </span><span class="p">{</span> <span class="linenos" data-line="16"></span><span class="w"> </span><span class="nx">fmt</span><span class="p">.</span><span class="nx">Println</span><span class="p">(</span><span class="s">"Error opening file:"</span><span class="p">,</span><span class="w"> </span><span class="nx">err</span><span class="p">)</span> <span class="linenos" data-line="17"></span><span class="w"> </span><span class="k">return</span> <span class="linenos" data-line="18"></span><span class="w"> </span><span class="p">}</span> <span class="linenos" data-line="19"></span><span class="w"> </span><span class="k">defer</span><span class="w"> </span><span class="nx">file</span><span class="p">.</span><span class="nx">Close</span><span class="p">()</span> <span class="linenos" data-line="20"></span> <span class="linenos" data-line="21"></span><span class="w"> </span><span class="nx">bitset</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="p">[</span><span class="nx">bitsetSize</span><span class="p">]</span><span class="kt">byte</span><span class="p">{}</span> <span class="linenos" data-line="22"></span> <span class="linenos" data-line="23"></span><span class="w"> </span><span class="c1">// Use a buffered scanner with a larger buffer</span> <span class="linenos" data-line="24"></span><span class="w"> </span><span class="nx">scanner</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nx">bufio</span><span class="p">.</span><span class="nx">NewScanner</span><span class="p">(</span><span class="nx">file</span><span class="p">)</span> <span class="linenos" data-line="25"></span><span class="w"> </span><span class="kd">const</span><span class="w"> </span><span class="nx">maxBuffer</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">64</span><span class="w"> </span><span class="o">*</span><span class="w"> </span><span class="mi">1024</span><span class="w"> </span><span class="c1">// 64 KB buffer</span> <span class="linenos" data-line="26"></span><span class="w"> </span><span class="nx">buf</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nb">make</span><span class="p">([]</span><span class="kt">byte</span><span class="p">,</span><span class="w"> </span><span class="mi">0</span><span class="p">,</span><span class="w"> </span><span class="nx">maxBuffer</span><span class="p">)</span> <span class="linenos" data-line="27"></span><span class="w"> </span><span class="nx">scanner</span><span class="p">.</span><span class="nx">Buffer</span><span class="p">(</span><span class="nx">buf</span><span class="p">,</span><span class="w"> </span><span class="nx">maxBuffer</span><span class="p">)</span> <span class="linenos" data-line="28"></span> <span class="linenos" data-line="29"></span><span class="w"> </span><span class="c1">// Process each line</span> <span class="linenos" data-line="30"></span><span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="nx">scanner</span><span class="p">.</span><span class="nx">Scan</span><span class="p">()</span><span class="w"> </span><span class="p">{</span> <span class="linenos" data-line="31"></span><span class="w"> </span><span class="nx">line</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nx">scanner</span><span class="p">.</span><span class="nx">Bytes</span><span class="p">()</span> <span class="linenos" data-line="32"></span> <span class="linenos" data-line="33"></span><span class="w"> </span><span class="c1">// Parse the IP address manually from bytes</span> <span class="linenos" data-line="34"></span><span class="w"> </span><span class="nx">ip</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nx">parseIPv4</span><span class="p">(</span><span class="nx">line</span><span class="p">)</span> <span class="linenos" data-line="35"></span><span class="w"> </span><span class="c1">// Set the bit</span> <span class="linenos" data-line="36"></span><span class="w"> </span><span class="nx">byteIndex</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nx">ip</span><span class="w"> </span><span class="o">>></span><span class="w"> </span><span class="mi">3</span><span class="w"> </span><span class="c1">// Divide by 8</span> <span class="linenos" data-line="37"></span><span class="w"> </span><span class="nx">bitIndex</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nx">ip</span><span class="w"> </span><span class="o">&</span><span class="w"> </span><span class="mi">7</span><span class="w"> </span><span class="c1">// Bit position 0-7</span> <span class="linenos" data-line="38"></span><span class="w"> </span><span class="nx">bitset</span><span class="p">[</span><span class="nx">byteIndex</span><span class="p">]</span><span class="w"> </span><span class="o">|=</span><span class="w"> </span><span class="mi">1</span><span class="w"> </span><span class="o"><<</span><span class="w"> </span><span class="nx">bitIndex</span> <span class="linenos" data-line="39"></span><span class="w"> </span><span class="p">}</span> <span class="linenos" data-line="40"></span> <span class="linenos" data-line="41"></span><span class="w"> </span><span class="c1">// Check for scanning errors</span> <span class="linenos" data-line="42"></span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="nx">err</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nx">scanner</span><span class="p">.</span><span class="nx">Err</span><span class="p">();</span><span class="w"> </span><span class="nx">err</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="kc">nil</span><span class="w"> </span><span class="p">{</span> <span class="linenos" data-line="43"></span><span class="w"> </span><span class="nx">fmt</span><span class="p">.</span><span class="nx">Println</span><span class="p">(</span><span class="s">"Error reading file:"</span><span class="p">,</span><span class="w"> </span><span class="nx">err</span><span class="p">)</span> <span class="linenos" data-line="44"></span><span class="w"> </span><span class="k">return</span> <span class="linenos" data-line="45"></span><span class="w"> </span><span class="p">}</span> <span class="linenos" data-line="46"></span> <span class="linenos" data-line="47"></span><span class="w"> </span><span class="kd">var</span><span class="w"> </span><span class="nx">count</span><span class="w"> </span><span class="kt">uint64</span> <span class="linenos" data-line="48"></span><span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="nx">i</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="mi">0</span><span class="p">;</span><span class="w"> </span><span class="nx">i</span><span class="w"> </span><span class="p"><</span><span class="w"> </span><span class="nx">bitsetSize</span><span class="p">;</span><span class="w"> </span><span class="nx">i</span><span class="o">++</span><span class="w"> </span><span class="p">{</span> <span class="linenos" data-line="49"></span><span class="w"> </span><span class="nx">count</span><span class="w"> </span><span class="o">+=</span><span class="w"> </span><span class="nb">uint64</span><span class="p">(</span><span class="nx">bits</span><span class="p">.</span><span class="nx">OnesCount8</span><span class="p">(</span><span class="nx">bitset</span><span class="p">[</span><span class="nx">i</span><span class="p">]))</span> <span class="linenos" data-line="50"></span><span class="w"> </span><span class="p">}</span> <span class="linenos" data-line="51"></span> <span class="linenos" data-line="52"></span><span class="w"> </span><span class="nx">fmt</span><span class="p">.</span><span class="nx">Println</span><span class="p">(</span><span class="s">"Number of unique IPv4 addresses:"</span><span class="p">,</span><span class="w"> </span><span class="nx">count</span><span class="p">)</span> <span class="linenos" data-line="53"></span><span class="p">}</span> <span class="linenos" data-line="54"></span> <span class="linenos" data-line="55"></span><span class="kd">func</span><span class="w"> </span><span class="nx">parseIPv4</span><span class="p">(</span><span class="nx">line</span><span class="w"> </span><span class="p">[]</span><span class="kt">byte</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="nx">ip</span><span class="w"> </span><span class="kt">uint32</span><span class="p">)</span><span class="w"> </span><span class="p">{</span> <span class="linenos" data-line="56"></span><span class="w"> </span><span class="nx">i</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="mi">0</span> <span class="linenos" data-line="57"></span> <span class="linenos" data-line="58"></span><span class="w"> </span><span class="c1">// Octet 1</span> <span class="linenos" data-line="59"></span><span class="w"> </span><span class="nx">n</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nb">uint32</span><span class="p">(</span><span class="nx">line</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="sc">'0'</span><span class="p">)</span> <span class="linenos" data-line="60"></span><span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="nx">i</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">1</span><span class="p">;</span><span class="w"> </span><span class="nx">line</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="sc">'.'</span><span class="p">;</span><span class="w"> </span><span class="nx">i</span><span class="o">++</span><span class="w"> </span><span class="p">{</span> <span class="linenos" data-line="61"></span><span class="w"> </span><span class="nx">n</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nx">n</span><span class="o">*</span><span class="mi">10</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="nb">uint32</span><span class="p">(</span><span class="nx">line</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="o">-</span><span class="sc">'0'</span><span class="p">)</span> <span class="linenos" data-line="62"></span><span class="w"> </span><span class="p">}</span> <span class="linenos" data-line="63"></span><span class="w"> </span><span class="nx">ip</span><span class="w"> </span><span class="o">|=</span><span class="w"> </span><span class="nx">n</span><span class="w"> </span><span class="o"><<</span><span class="w"> </span><span class="mi">24</span> <span class="linenos" data-line="64"></span><span class="w"> </span><span class="nx">i</span><span class="o">++</span><span class="w"> </span><span class="c1">// Skip the dot</span> <span class="linenos" data-line="65"></span> <span class="linenos" data-line="66"></span><span class="w"> </span><span class="c1">// Octet 2</span> <span class="linenos" data-line="67"></span><span class="w"> </span><span class="nx">n</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nb">uint32</span><span class="p">(</span><span class="nx">line</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="sc">'0'</span><span class="p">)</span> <span class="linenos" data-line="68"></span><span class="w"> </span><span class="nx">i</span><span class="o">++</span> <span class="linenos" data-line="69"></span><span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="p">;</span><span class="w"> </span><span class="nx">line</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="sc">'.'</span><span class="p">;</span><span class="w"> </span><span class="nx">i</span><span class="o">++</span><span class="w"> </span><span class="p">{</span> <span class="linenos" data-line="70"></span><span class="w"> </span><span class="nx">n</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nx">n</span><span class="o">*</span><span class="mi">10</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="nb">uint32</span><span class="p">(</span><span class="nx">line</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="o">-</span><span class="sc">'0'</span><span class="p">)</span> <span class="linenos" data-line="71"></span><span class="w"> </span><span class="p">}</span> <span class="linenos" data-line="72"></span><span class="w"> </span><span class="nx">ip</span><span class="w"> </span><span class="o">|=</span><span class="w"> </span><span class="nx">n</span><span class="w"> </span><span class="o"><<</span><span class="w"> </span><span class="mi">16</span> <span class="linenos" data-line="73"></span><span class="w"> </span><span class="nx">i</span><span class="o">++</span><span class="w"> </span><span class="c1">// Skip the dot</span> <span class="linenos" data-line="74"></span> <span class="linenos" data-line="75"></span><span class="w"> </span><span class="c1">// Octet 3</span> <span class="linenos" data-line="76"></span><span class="w"> </span><span class="nx">n</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nb">uint32</span><span class="p">(</span><span class="nx">line</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="sc">'0'</span><span class="p">)</span> <span class="linenos" data-line="77"></span><span class="w"> </span><span class="nx">i</span><span class="o">++</span> <span class="linenos" data-line="78"></span><span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="p">;</span><span class="w"> </span><span class="nx">line</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="sc">'.'</span><span class="p">;</span><span class="w"> </span><span class="nx">i</span><span class="o">++</span><span class="w"> </span><span class="p">{</span> <span class="linenos" data-line="79"></span><span class="w"> </span><span class="nx">n</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nx">n</span><span class="o">*</span><span class="mi">10</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="nb">uint32</span><span class="p">(</span><span class="nx">line</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="o">-</span><span class="sc">'0'</span><span class="p">)</span> <span class="linenos" data-line="80"></span><span class="w"> </span><span class="p">}</span> <span class="linenos" data-line="81"></span><span class="w"> </span><span class="nx">ip</span><span class="w"> </span><span class="o">|=</span><span class="w"> </span><span class="nx">n</span><span class="w"> </span><span class="o"><<</span><span class="w"> </span><span class="mi">8</span> <span class="linenos" data-line="82"></span><span class="w"> </span><span class="nx">i</span><span class="o">++</span><span class="w"> </span><span class="c1">// Skip the dot</span> <span class="linenos" data-line="83"></span> <span class="linenos" data-line="84"></span><span class="w"> </span><span class="c1">// Octet 4</span> <span class="linenos" data-line="85"></span><span class="w"> </span><span class="nx">n</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nb">uint32</span><span class="p">(</span><span class="nx">line</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="sc">'0'</span><span class="p">)</span> <span class="linenos" data-line="86"></span><span class="w"> </span><span class="nx">i</span><span class="o">++</span> <span class="linenos" data-line="87"></span><span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="p">;</span><span class="w"> </span><span class="nx">i</span><span class="w"> </span><span class="p"><</span><span class="w"> </span><span class="nb">len</span><span class="p">(</span><span class="nx">line</span><span class="p">);</span><span class="w"> </span><span class="nx">i</span><span class="o">++</span><span class="w"> </span><span class="p">{</span> <span class="linenos" data-line="88"></span><span class="w"> </span><span class="nx">n</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nx">n</span><span class="o">*</span><span class="mi">10</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="nb">uint32</span><span class="p">(</span><span class="nx">line</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="o">-</span><span class="sc">'0'</span><span class="p">)</span> <span class="linenos" data-line="89"></span><span class="w"> </span><span class="p">}</span> <span class="linenos" data-line="90"></span><span class="w"> </span><span class="nx">ip</span><span class="w"> </span><span class="o">|=</span><span class="w"> </span><span class="nx">n</span> <span class="linenos" data-line="91"></span> <span class="linenos" data-line="92"></span><span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="nx">ip</span> <span class="linenos" data-line="93"></span><span class="p">}</span> </pre></div> <div class="mw-heading mw-heading2"><h2 id="Language_support">Language support</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Bit_array&action=edit&section=11" title="Edit section: Language support"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The <a href="/wiki/APL_(programming_language)" title="APL (programming language)">APL programming language</a> fully supports bit arrays of arbitrary shape and size as a Boolean datatype distinct from integers. All major implementations (<a href="/wiki/APL_(programming_language)#Execution" title="APL (programming language)">Dyalog APL, APL2, APL Next, NARS2000, Gnu APL</a>, etc.) pack the bits densely into whatever size the machine word is. Bits may be accessed individually via the usual indexing notation (A[3]) as well as through all of the usual primitive functions and operators where they are often operated on using a special case algorithm such as summing the bits via a table lookup of bytes. </p><p>The <a href="/wiki/C_(programming_language)" title="C (programming language)">C programming language</a>'s <i><a href="/wiki/Bit_field" title="Bit field">bit fields</a></i>, pseudo-objects found in structs with size equal to some number of bits, are in fact small bit arrays; they are limited in that they cannot span words. Although they give a convenient syntax, the bits are still accessed using bytewise operators on most machines, and they can only be defined statically (like C's static arrays, their sizes are fixed at compile-time). It is also a common idiom for C programmers to use words as small bit arrays and access bits of them using bit operators. A widely available header file included in the <a href="/wiki/X11" class="mw-redirect" title="X11">X11</a> system, xtrapbits.h, is “a portable way for systems to define bit field manipulation of arrays of bits.” A more explanatory description of aforementioned approach can be found in the <a rel="nofollow" class="external text" href="http://c-faq.com/misc/bitsets.html">comp.lang.c faq</a>. </p><p>In <a href="/wiki/C%2B%2B" title="C++">C++</a>, although individual <code>bool</code>s typically occupy the same space as a byte or an integer, the <a href="/wiki/Standard_Template_Library" title="Standard Template Library">STL</a> type <code>vector<bool></code> is a <a href="/wiki/Partial_template_specialization" title="Partial template specialization">partial template specialization</a> in which bits are packed as a space efficiency optimization. Since bytes (and not bits) are the smallest addressable unit in C++, the [] operator does <i>not</i> return a reference to an element, but instead returns a <a href="/wiki/Proxy_pattern" title="Proxy pattern">proxy reference</a>. This might seem a minor point, but it means that <code>vector<bool></code> is <i>not</i> a standard STL container, which is why the use of <code>vector<bool></code> is generally discouraged. Another unique STL class, <code>bitset</code>,<sup id="cite_ref-c++_3-0" class="reference"><a href="#cite_note-c++-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> creates a vector of bits fixed at a particular size at compile-time, and in its interface and syntax more resembles the idiomatic use of words as bit sets by C programmers. It also has some additional power, such as the ability to efficiently count the number of bits that are set. The <a href="/wiki/Boost_C%2B%2B_Libraries" class="mw-redirect" title="Boost C++ Libraries">Boost C++ Libraries</a> provide a <code>dynamic_bitset</code> class<sup id="cite_ref-boost_4-0" class="reference"><a href="#cite_note-boost-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> whose size is specified at run-time. </p><p>The <a href="/wiki/D_programming_language" class="mw-redirect" title="D programming language">D programming language</a> provides bit arrays in its standard library, Phobos, in <code>std.bitmanip</code>. As in C++, the [] operator does not return a reference, since individual bits are not directly addressable on most hardware, but instead returns a <code>bool</code>. </p><p>In <a href="/wiki/Java_(programming_language)" title="Java (programming language)">Java</a>, the class <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/19/docs/api/java.base/java/util/BitSet.html">BitSet</a></code> creates a bit array that is then manipulated with functions named after bitwise operators familiar to C programmers. Unlike the <code>bitset</code> in C++, the Java <code>BitSet</code> does not have a "size" state (it has an effectively infinite size, initialized with 0 bits); a bit can be set or tested at any index. In addition, there is a class <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/19/docs/api/java.base/java/util/EnumSet.html">EnumSet</a></code>, which represents a Set of values of an <a href="/wiki/Enumerated_type" title="Enumerated type">enumerated type</a> internally as a bit vector, as a safer alternative to bit fields. </p><p>The <a href="/wiki/.NET_Framework" title=".NET Framework">.NET Framework</a> supplies a <code>BitArray</code> collection class. It stores bits using an array of type <code>int</code> (each element in the array usually represents 32 bits).<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> The class supports random access and bitwise operators, can be iterated over, and its <code>Length</code> property can be changed to grow or truncate it. </p><p>Although <a href="/wiki/Standard_ML" title="Standard ML">Standard ML</a> has no support for bit arrays, Standard ML of New Jersey has an extension, the <code>BitArray</code> structure, in its SML/NJ Library. It is not fixed in size and supports set operations and bit operations, including, unusually, shift operations. </p><p><a href="/wiki/Haskell_(programming_language)" class="mw-redirect" title="Haskell (programming language)">Haskell</a> likewise currently lacks standard support for bitwise operations, but both <a href="/wiki/Glasgow_Haskell_Compiler" title="Glasgow Haskell Compiler">GHC</a> and Hugs provide a <code>Data.Bits</code> module with assorted bitwise functions and operators, including shift and rotate operations and an "unboxed" array over Boolean values may be used to model a Bit array, although this lacks support from the former module. </p><p>In <a href="/wiki/Perl" title="Perl">Perl</a>, strings can be used as expandable bit arrays. They can be manipulated using the usual bitwise operators (<code>~ | & ^</code>),<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> and individual bits can be tested and set using the <i>vec</i> function.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> </p><p>In <a href="/wiki/Ruby_(programming_language)" title="Ruby (programming language)">Ruby</a>, you can access (but not set) a bit of an integer (<code>Fixnum</code> or <code>Bignum</code>) using the bracket operator (<code>[]</code>), as if it were an array of bits. </p><p>Apple's <a href="/wiki/Core_Foundation" title="Core Foundation">Core Foundation</a> library contains <a rel="nofollow" class="external text" href="https://developer.apple.com/library/mac/#documentation/CoreFoundation/Reference/CFBitVectorRef/Reference/reference.html">CFBitVector</a> and <a rel="nofollow" class="external text" href="https://developer.apple.com/library/mac/#documentation/CoreFoundation/Reference/CFMutableBitVectorRef/Reference/reference.html#//apple_ref/doc/uid/20001500">CFMutableBitVector</a> structures. </p><p><a href="/wiki/PL/I" title="PL/I">PL/I</a> supports arrays of <i>bit strings</i> of arbitrary length, which may be either fixed-length or varying. The array elements may be <i>aligned</i>— each element begins on a byte or word boundary— or <i>unaligned</i>— elements immediately follow each other with no padding. </p><p><a href="/wiki/PL/pgSQL" title="PL/pgSQL">PL/pgSQL</a> and PostgreSQL's SQL support <i>bit strings</i> as native type. There are two SQL bit types: <code>bit(<i><code>n</code></i>)</code> and <code>bit varying(<i><code>n</code></i>)</code>, where <i><code>n</code></i> is a positive integer.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> </p><p>Hardware description languages such as <a href="/wiki/VHDL" title="VHDL">VHDL</a>, <a href="/wiki/Verilog" title="Verilog">Verilog</a>, and <a href="/wiki/SystemVerilog" title="SystemVerilog">SystemVerilog</a> natively support bit vectors as these are used to model storage elements like <a href="/wiki/Flip-flop_(electronics)" title="Flip-flop (electronics)">flip-flops</a>, hardware busses and hardware signals in general. In hardware verification languages such as OpenVera, <a href="/wiki/E_(verification_language)" title="E (verification language)"><i>e</i></a> and <a href="/wiki/SystemVerilog" title="SystemVerilog">SystemVerilog</a>, bit vectors are used to sample values from the hardware models, and to represent data that is transferred to hardware during simulations. </p><p><a href="/wiki/Common_Lisp" title="Common Lisp">Common Lisp</a> provides multi-dimensional bit arrays. A one-dimensional <code>bit-vector</code> implementation is provided as a special case of the built-in <code>array</code>, acting in a dual capacity as a class and a type specifier.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> Bit arrays (and thus bit vectors) relies on the general <code>make-array</code> function to be configured with an element type of <code>bit</code>, which optionally permits a bit vector to be designated as dynamically resizable. The <code>bit-vector</code>, however, is not infinite in extent. A more restricted <code>simple-bit-vector</code> type exists, which explicitly excludes the dynamic characteristics.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> Bit vectors are represented as, and can be constructed in a more concise fashion by, the <i>reader macro</i> <code>#*<i>bits</i></code>.<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> In addition to the general functions applicable to all arrays, dedicated operations exist for bit arrays. Single bits may be accessed and modified using the <code>bit</code> and <code>sbit</code> functions<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> and an extensive number of logical operations is supported.<sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Bit_array&action=edit&section=12" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Arithmetic_logic_unit" title="Arithmetic logic unit">Arithmetic logic unit</a></li> <li><a href="/wiki/Binary_code" title="Binary code">Binary code</a></li> <li><a href="/wiki/Binary_numeral_system" class="mw-redirect" title="Binary numeral system">Binary numeral system</a></li> <li><a href="/wiki/Bitboard" title="Bitboard">Bitboard</a> Chess and similar games.</li> <li><a href="/wiki/Bit_field" title="Bit field">Bit field</a></li> <li><a href="/wiki/Bitmap_index" title="Bitmap index">Bitmap index</a></li> <li><a href="/wiki/Bitstream" title="Bitstream">Bitstream</a></li> <li><a href="/wiki/Finite_field" title="Finite field">Finite field</a> of 2 elements, or <a href="/wiki/GF(2)" title="GF(2)">GF(2)</a></li> <li><a href="/wiki/Judy_array" title="Judy array">Judy array</a></li> <li><a href="/wiki/Variable-length_code" title="Variable-length code">Variable-length code</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Bit_array&action=edit&section=13" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap mw-references-columns"><ol class="references"> <li id="cite_note-linux-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-linux_1-0">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.kernel.org/doc/html/latest/admin-guide/sysrq.html">"Linux Magic System Request Key Hacks"</a>. <a href="/wiki/Kernel.org" title="Kernel.org">Kernel.org</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Linux+Magic+System+Request+Key+Hacks&rft.pub=Kernel.org&rft_id=https%3A%2F%2Fwww.kernel.org%2Fdoc%2Fhtml%2Flatest%2Fadmin-guide%2Fsysrq.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABit+array" class="Z3988"></span></span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><a href="/wiki/Irving_Copilowish" class="mw-redirect" title="Irving Copilowish">Irving Copilowish</a> (December 1948) "Matrix development of the calculus of relations", <a href="/wiki/Journal_of_Symbolic_Logic" title="Journal of Symbolic Logic">Journal of Symbolic Logic</a> 13(4): 193–203 <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2267134?seq=1#page_scan_tab_contents">Jstor link</a></span> </li> <li id="cite_note-c++-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-c++_3-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.sgi.com/tech/stl/bitset.html">"SGI.com Tech Archive Resources now retired"</a>. <a href="/wiki/Silicon_Graphics" title="Silicon Graphics">SGI</a>. 2 January 2018.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=SGI.com+Tech+Archive+Resources+now+retired&rft.pub=SGI&rft.date=2018-01-02&rft_id=http%3A%2F%2Fwww.sgi.com%2Ftech%2Fstl%2Fbitset.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABit+array" class="Z3988"></span></span> </li> <li id="cite_note-boost-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-boost_4-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.boost.org/libs/dynamic_bitset/dynamic_bitset.html">"dynamic_bitset<Block, Allocator> - 1.66.0"</a>. <i>www.boost.org</i>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=www.boost.org&rft.atitle=dynamic_bitset%3CBlock%2C+Allocator%3E+-+1.66.0&rft_id=http%3A%2F%2Fwww.boost.org%2Flibs%2Fdynamic_bitset%2Fdynamic_bitset.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABit+array" class="Z3988"></span></span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://github.com/microsoft/referencesource/blob/master/mscorlib/system/collections/bitarray.cs">".NET mscorlib source code"</a>. <i>github.com/microsoft</i>. 15 October 2021.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=github.com%2Fmicrosoft&rft.atitle=.NET+mscorlib+source+code&rft.date=2021-10-15&rft_id=https%3A%2F%2Fgithub.com%2Fmicrosoft%2Freferencesource%2Fblob%2Fmaster%2Fmscorlib%2Fsystem%2Fcollections%2Fbitarray.cs&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABit+array" class="Z3988"></span></span> </li> <li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://perldoc.perl.org/perlop.html#Bitwise-String-Operators">"perlop - perldoc.perl.org"</a>. <i>perldoc.perl.org</i>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=perldoc.perl.org&rft.atitle=perlop+-+perldoc.perl.org&rft_id=http%3A%2F%2Fperldoc.perl.org%2Fperlop.html%23Bitwise-String-Operators&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABit+array" class="Z3988"></span></span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://perldoc.perl.org/functions/vec.html">"vec - perldoc.perl.org"</a>. <i>perldoc.perl.org</i>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=perldoc.perl.org&rft.atitle=vec+-+perldoc.perl.org&rft_id=http%3A%2F%2Fperldoc.perl.org%2Ffunctions%2Fvec.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABit+array" class="Z3988"></span></span> </li> <li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.postgresql.org/docs/current/datatype-bit.html">"8.10. Bit String Types"</a>. 30 September 2021.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=8.10.+Bit+String+Types&rft.date=2021-09-30&rft_id=https%3A%2F%2Fwww.postgresql.org%2Fdocs%2Fcurrent%2Fdatatype-bit.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABit+array" class="Z3988"></span></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.lispworks.com/documentation/HyperSpec/Body/t_bt_vec.htm">"CLHS: System Class BIT-VECTOR"</a>. <i>www.lispworks.com</i>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=www.lispworks.com&rft.atitle=CLHS%3A+System+Class+BIT-VECTOR&rft_id=http%3A%2F%2Fwww.lispworks.com%2Fdocumentation%2FHyperSpec%2FBody%2Ft_bt_vec.htm&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABit+array" class="Z3988"></span></span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.lispworks.com/documentation/HyperSpec/Body/t_smp_bt.htm">"CLHS: Type SIMPLE-BIT-VECTOR"</a>. <i>www.lispworks.com</i>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=www.lispworks.com&rft.atitle=CLHS%3A+Type+SIMPLE-BIT-VECTOR&rft_id=http%3A%2F%2Fwww.lispworks.com%2Fdocumentation%2FHyperSpec%2FBody%2Ft_smp_bt.htm&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABit+array" class="Z3988"></span></span> </li> <li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.lispworks.com/documentation/HyperSpec/Body/02_dhd.htm">"CLHS: Section 2.4.8.4"</a>. <i>www.lispworks.com</i>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=www.lispworks.com&rft.atitle=CLHS%3A+Section+2.4.8.4&rft_id=http%3A%2F%2Fwww.lispworks.com%2Fdocumentation%2FHyperSpec%2FBody%2F02_dhd.htm&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABit+array" class="Z3988"></span></span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.lispworks.com/documentation/HyperSpec/Body/f_bt_sb.htm">"CLHS: Accessor BIT, SBIT"</a>. <i>www.lispworks.com</i>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=www.lispworks.com&rft.atitle=CLHS%3A+Accessor+BIT%2C+SBIT&rft_id=http%3A%2F%2Fwww.lispworks.com%2Fdocumentation%2FHyperSpec%2FBody%2Ff_bt_sb.htm&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABit+array" class="Z3988"></span></span> </li> <li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.lispworks.com/documentation/HyperSpec/Body/f_bt_and.htm">"CLHS: Function BIT-AND, BIT-ANDC1, BIT-ANDC2..."</a> <i>www.lispworks.com</i>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=www.lispworks.com&rft.atitle=CLHS%3A+Function+BIT-AND%2C+BIT-ANDC1%2C+BIT-ANDC2...&rft_id=http%3A%2F%2Fwww.lispworks.com%2Fdocumentation%2FHyperSpec%2FBody%2Ff_bt_and.htm&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABit+array" class="Z3988"></span></span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Bit_array&action=edit&section=14" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a rel="nofollow" class="external text" href="http://www-cs-faculty.stanford.edu/~knuth/fasc1a.ps.gz">mathematical bases</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20191016044101/http://www-cs-faculty.stanford.edu/~knuth/fasc1a.ps.gz">Archived</a> 2019-10-16 at the <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a> by Pr. D.E.Knuth</li> <li><a rel="nofollow" class="external text" href="http://www.gotw.ca/publications/N1185.pdf">vector<bool> Is Nonconforming, and Forces Optimization Choice</a></li> <li><a rel="nofollow" class="external text" href="http://www.gotw.ca/publications/N1211.pdf">vector<bool>: More Problems, Better Solutions</a></li></ul> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Data_structures216" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374" /><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Data_structures" title="Template:Data structures"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Data_structures" title="Template talk:Data structures"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Data_structures" title="Special:EditPage/Template:Data structures"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Data_structures216" style="font-size:114%;margin:0 4em"><a href="/wiki/Data_structure" title="Data structure">Data structures</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Types</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Collection_(abstract_data_type)" title="Collection (abstract data type)">Collection</a></li> <li><a href="/wiki/Container_(abstract_data_type)" title="Container (abstract data type)">Container</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Abstract_data_type" title="Abstract data type">Abstract</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Associative_array" title="Associative array">Associative array</a> <ul><li><a href="/wiki/Multimap" title="Multimap">Multimap</a></li> <li><a href="/wiki/Retrieval_Data_Structure" title="Retrieval Data Structure">Retrieval Data Structure</a></li></ul></li> <li><a href="/wiki/List_(abstract_data_type)" title="List (abstract data type)">List</a></li> <li><a href="/wiki/Stack_(abstract_data_type)" title="Stack (abstract data type)">Stack</a></li> <li><a href="/wiki/Queue_(abstract_data_type)" title="Queue (abstract data type)">Queue</a> <ul><li><a href="/wiki/Double-ended_queue" title="Double-ended queue">Double-ended queue</a></li></ul></li> <li><a href="/wiki/Priority_queue" title="Priority queue">Priority queue</a> <ul><li><a href="/wiki/Double-ended_priority_queue" title="Double-ended priority queue">Double-ended priority queue</a></li></ul></li> <li><a href="/wiki/Set_(abstract_data_type)" title="Set (abstract data type)">Set</a> <ul><li><a href="/wiki/Set_(abstract_data_type)#Multiset" title="Set (abstract data type)">Multiset</a></li> <li><a href="/wiki/Disjoint-set_data_structure" title="Disjoint-set data structure">Disjoint-set</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Array_(data_structure)" title="Array (data structure)">Arrays</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a class="mw-selflink selflink">Bit array</a></li> <li><a href="/wiki/Circular_buffer" title="Circular buffer">Circular buffer</a></li> <li><a href="/wiki/Dynamic_array" title="Dynamic array">Dynamic array</a></li> <li><a href="/wiki/Hash_table" title="Hash table">Hash table</a></li> <li><a href="/wiki/Hashed_array_tree" title="Hashed array tree">Hashed array tree</a></li> <li><a href="/wiki/Sparse_matrix" title="Sparse matrix">Sparse matrix</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Linked_data_structure" title="Linked data structure">Linked</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Association_list" title="Association list">Association list</a></li> <li><a href="/wiki/Linked_list" title="Linked list">Linked list</a></li> <li><a href="/wiki/Skip_list" title="Skip list">Skip list</a></li> <li><a href="/wiki/Unrolled_linked_list" title="Unrolled linked list">Unrolled linked list</a></li> <li><a href="/wiki/XOR_linked_list" title="XOR linked list">XOR linked list</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">Trees</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/B-tree" title="B-tree">B-tree</a></li> <li><a href="/wiki/Binary_search_tree" title="Binary search tree">Binary search tree</a> <ul><li><a href="/wiki/AA_tree" title="AA tree">AA tree</a></li> <li><a href="/wiki/AVL_tree" title="AVL tree">AVL tree</a></li> <li><a href="/wiki/Red%E2%80%93black_tree" title="Red–black tree">Red–black tree</a></li> <li><a href="/wiki/Self-balancing_binary_search_tree" title="Self-balancing binary search tree">Self-balancing tree</a></li> <li><a href="/wiki/Splay_tree" title="Splay tree">Splay tree</a></li></ul></li> <li><a href="/wiki/Heap_(data_structure)" title="Heap (data structure)">Heap</a> <ul><li><a href="/wiki/Binary_heap" title="Binary heap">Binary heap</a></li> <li><a href="/wiki/Binomial_heap" title="Binomial heap">Binomial heap</a></li> <li><a href="/wiki/Fibonacci_heap" title="Fibonacci heap">Fibonacci heap</a></li></ul></li> <li><a href="/wiki/R-tree" title="R-tree">R-tree</a> <ul><li><a href="/wiki/R*_tree" class="mw-redirect" title="R* tree">R* tree</a></li> <li><a href="/wiki/R%2B_tree" title="R+ tree">R+ tree</a></li> <li><a href="/wiki/Hilbert_R-tree" title="Hilbert R-tree">Hilbert R-tree</a></li></ul></li> <li><a href="/wiki/Trie" title="Trie">Trie</a> <ul><li><a href="/wiki/Hash_tree_(persistent_data_structure)" title="Hash tree (persistent data structure)">Hash tree</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Graph_(abstract_data_type)" title="Graph (abstract data type)">Graphs</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Binary_decision_diagram" title="Binary decision diagram">Binary decision diagram</a></li> <li><a href="/wiki/Directed_acyclic_graph" title="Directed acyclic graph">Directed acyclic graph</a></li> <li><a href="/wiki/Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">Directed acyclic word graph</a></li></ul> </div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div> <ul><li><a href="/wiki/List_of_data_structures" title="List of data structures">List of data structures</a></li></ul> </div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?useformat=desktop&type=1x1&usesul3=0" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Bit_array&oldid=1279839196">https://en.wikipedia.org/w/index.php?title=Bit_array&oldid=1279839196</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Arrays" title="Category:Arrays">Arrays</a></li><li><a href="/wiki/Category:Bit_data_structures" title="Category:Bit data structures">Bit data structures</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_matches_Wikidata" title="Category:Short description matches Wikidata">Short description matches Wikidata</a></li><li><a href="/wiki/Category:Articles_needing_additional_references_from_December_2010" title="Category:Articles needing additional references from December 2010">Articles needing additional references from December 2010</a></li><li><a href="/wiki/Category:All_articles_needing_additional_references" title="Category:All articles needing additional references">All articles needing additional references</a></li><li><a href="/wiki/Category:Webarchive_template_wayback_links" title="Category:Webarchive template wayback links">Webarchive template wayback links</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 10 March 2025, at 21:58<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Bit_array&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><picture><source media="(min-width: 500px)" srcset="/static/images/footer/wikimedia-button.svg" width="84" height="29"><img src="/static/images/footer/wikimedia.svg" width="25" height="25" alt="Wikimedia Foundation" lang="en" loading="lazy"></picture></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><picture><source media="(min-width: 500px)" srcset="/w/resources/assets/poweredby_mediawiki.svg" width="88" height="31"><img src="/w/resources/assets/mediawiki_compact.svg" alt="Powered by MediaWiki" lang="en" width="25" height="25" loading="lazy"></picture></a></li> </ul> </footer> </div> </div> </div> <div class="vector-header-container vector-sticky-header-container"> <div id="vector-sticky-header" class="vector-sticky-header"> <div class="vector-sticky-header-start"> <div class="vector-sticky-header-icon-start vector-button-flush-left vector-button-flush-right" aria-hidden="true"> <button class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-sticky-header-search-toggle" tabindex="-1" data-event-name="ui.vector-sticky-search-form.icon"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </button> </div> <div role="search" class="vector-search-box-vue vector-search-box-show-thumbnail vector-search-box"> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail"> <form action="/w/index.php" id="vector-sticky-search-form" class="cdx-search-input cdx-search-input--has-end-button"> <div class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia"> <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <div class="vector-sticky-header-context-bar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-sticky-header-toc" class="vector-dropdown mw-portlet mw-portlet-sticky-header-toc vector-sticky-header-toc vector-button-flush-left" > <input type="checkbox" id="vector-sticky-header-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-sticky-header-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-sticky-header-toc-label" for="vector-sticky-header-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-sticky-header-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div class="vector-sticky-header-context-bar-primary" aria-hidden="true" ><span class="mw-page-title-main">Bit array</span></div> </div> </div> <div class="vector-sticky-header-end" aria-hidden="true"> <div class="vector-sticky-header-icons"> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-talk-sticky-header" tabindex="-1" data-event-name="talk-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbles mw-ui-icon-wikimedia-speechBubbles"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-subject-sticky-header" tabindex="-1" data-event-name="subject-sticky-header"><span class="vector-icon mw-ui-icon-article mw-ui-icon-wikimedia-article"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-history-sticky-header" tabindex="-1" data-event-name="history-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-history mw-ui-icon-wikimedia-wikimedia-history"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only mw-watchlink" id="ca-watchstar-sticky-header" tabindex="-1" data-event-name="watch-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-star mw-ui-icon-wikimedia-wikimedia-star"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-edit-sticky-header" tabindex="-1" data-event-name="wikitext-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-wikiText mw-ui-icon-wikimedia-wikimedia-wikiText"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-ve-edit-sticky-header" tabindex="-1" data-event-name="ve-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-edit mw-ui-icon-wikimedia-wikimedia-edit"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-viewsource-sticky-header" tabindex="-1" data-event-name="ve-edit-protected-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-editLock mw-ui-icon-wikimedia-wikimedia-editLock"></span> <span></span> </a> </div> <div class="vector-sticky-header-buttons"> <button class="cdx-button cdx-button--weight-quiet mw-interlanguage-selector" id="p-lang-btn-sticky-header" tabindex="-1" data-event-name="ui.dropdown-p-lang-btn-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-language mw-ui-icon-wikimedia-wikimedia-language"></span> <span>15 languages</span> </button> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive" id="ca-addsection-sticky-header" tabindex="-1" data-event-name="addsection-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbleAdd-progressive mw-ui-icon-wikimedia-speechBubbleAdd-progressive"></span> <span>Add topic</span> </a> </div> <div class="vector-sticky-header-icon-end"> <div class="vector-user-links"> </div> </div> </div> </div> </div> <div class="mw-portlet mw-portlet-dock-bottom emptyPortlet" id="p-dock-bottom"> <ul> </ul> </div> <script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-7556665f6-j6vpb","wgBackendResponseTime":146,"wgPageParseReport":{"limitreport":{"cputime":"0.393","walltime":"0.560","ppvisitednodes":{"value":1038,"limit":1000000},"postexpandincludesize":{"value":34978,"limit":2097152},"templateargumentsize":{"value":868,"limit":2097152},"expansiondepth":{"value":9,"limit":100},"expensivefunctioncount":{"value":4,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":69990,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 464.208 1 -total"," 30.41% 141.188 1 Template:Reflist"," 26.78% 124.298 12 Template:Cite_web"," 19.31% 89.654 1 Template:Short_description"," 18.02% 83.672 1 Template:Data_structures"," 17.46% 81.039 1 Template:Navbox"," 12.98% 60.269 1 Template:More_citations_needed"," 11.90% 55.258 1 Template:Ambox"," 8.58% 39.838 2 Template:Pagetype"," 8.35% 38.739 4 Template:Main_other"]},"scribunto":{"limitreport-timeusage":{"value":"0.240","limit":"10.000"},"limitreport-memusage":{"value":5829441,"limit":52428800}},"cachereport":{"origin":"mw-api-ext.codfw.next-6ccb7746cc-xjnh9","timestamp":"20250310215816","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Bit array","url":"https:\/\/en.wikipedia.org\/wiki\/Bit_array","sameAs":"http:\/\/www.wikidata.org\/entity\/Q1992074","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q1992074","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2004-11-20T05:58:08Z","dateModified":"2025-03-10T21:58:15Z","headline":"array data structure that compactly stores bits"}</script> </body> </html>