2e:null 2f:["$","title",null,{"children":"Bit Twiddling Problems | Brooks Mershon | Observable"}] 34:[] 32:{"id":"eddf47711ba04b1d","slug":"bit-twiddling-problems","title":"Bit Twiddling Problems","thumbnail":"176778955dbb12471c425ca8d49ccc08e72be7373d901654bbe0993184e32734","access_level":"public","create_time":"$D2018-10-23T00:56:12.601Z","update_time":"$D2018-11-05T18:54:38.627Z","view_time":null,"first_public_time":"$D2018-11-04T20:50:55.283Z","has_unpublished_edits":null,"fork":{"id":"a47c3e170f12a93f","slug":"array-problems","title":"Array Problems","owner":{"id":"98f3645644c53887","login":"bmershon","name":"Brooks Mershon"}},"stars":1,"starred":false,"owner":{"type":"team","id":"98f3645644c53887","login":"bmershon","name":"Brooks Mershon","avatar_url":"https://avatars-next.observableusercontent.com/5641716d4c51e1abb1d4b3a4696b29ad7f633a87b86220947699a1f612083c33","tier":"starter_2024"},"version":329,"publish_version":329,"role":null,"authored":false,"authors":[{"type":"individual","id":"f11356ce54f25c8b","login":"bmershon","name":"Brooks Mershon","avatar_url":"https://avatars-next.observableusercontent.com/5331359238b7666c1cb986b48f8e69f0c357feba767a709324063cd52818c420","tier":null}],"members":[{"type":"individual","id":"f11356ce54f25c8b","login":"bmershon","name":"Brooks Mershon","avatar_url":"https://avatars-next.observableusercontent.com/5331359238b7666c1cb986b48f8e69f0c357feba767a709324063cd52818c420","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"title":"Bit Twiddling Problems","cells":[{"id":0,"value":"md`# Bit Twiddling Problems`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":78,"value":"md`## 1. Test kth bit.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":79,"value":"function isBitSet(n, k) {\n return n & (1 << k) != 0;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":85,"value":"isBitSet(5, 2)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":98,"value":"md`## 2. Set kth bit.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":109,"value":"function setBit(n, k) {\n return n | (1 << k);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":111,"value":"setBit(5, 1) // 0111 (\"7 in base 10\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":120,"value":"md`## 3. Turn off kth bit`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":125,"value":"function unsetBit(n, k) {\n return n & ~(1 << k); // XOR\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":129,"value":"setBit(unsetBit(unsetBit(5, 0), 2), 5)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":149,"value":"md`## 4. Toggle kth bit`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":150,"value":"function toggleBit(n, k) {\n return n ^ (1 << k);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":156,"value":"toggleBit(toggleBit(5, 2), 5) // 5 -> 1 --> 33 ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":159,"value":"md`## 5. Check if a number is a power of 2`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":162,"value":"function isPowerOf2(n) {\n return 0 == (n & (n - 1)); // two's complement, test for overlap\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":211,"value":"isPowerOf2(32)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":213,"value":"md`## 6. Get index of highest order bit`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":214,"value":"function highestOrderBit(n) {\n let test = 31; \n \n if (n == 0) return -1;\n \n while (test > 0) {\n if (n & (1 << test)) {\n return test;\n }\n test--;\n }\n \n \n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":219,"value":"highestOrderBit(17) // 10001","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":226,"value":"highestOrderBit(32) // 100000","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":233,"value":"highestOrderBit(35) // 100011","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":239,"value":"// Unsigned integer. Assume 32 bits unsigned integer.\n// A kind of cheeky solution that uses parseInt and toString with\n// a binary radix specified.\nfunction reverseBits(n) {\n const BIT_SIZE = 32;\n \n let s = n.toString(2);\n \n for (let i = BIT_SIZE - s.length; i > 0; i--) {\n s = \"0\" + s; // left pad zeros;\n }\n \n return parseInt(s.split('').reverse().join(''), 2);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":249,"value":"highestOrderBit(43261596) // 00000010100101000001111010011100 in binary, 32 bits in total","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":266,"value":"reverseBits(43261596)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W34","stdlib":"1","titling":"auto"}} 33:"$32:body"