f28bf0f3.cea09604.js

(window.webpackJsonp=window.webpackJsonp||[]).push([[68],{140:function(e,n,t){"use strict";t.r(n),t.d(n,"frontMatter",(function(){return a})),t.d(n,"metadata",(function(){return c})),t.d(n,"toc",(function(){return u})),t.d(n,"default",(function(){return s}));var r=t(147),o=t(149),i=(t(0),t(148)),a={id:"Introduction",title:"Bit Manipulation",sidebar_label:"Introduction"},c={unversionedId:"Patterns/BitManipulation/Introduction",id:"Patterns/BitManipulation/Introduction",isDocsHomePage:!1,title:"Bit Manipulation",description:"Power of 2",source:"@site/docs/Patterns/BitManipulation/Introduction.md",slug:"/Patterns/BitManipulation/Introduction",permalink:"/docs/Patterns/BitManipulation/Introduction",version:"current",sidebar_label:"Introduction",sidebar:"Patterns",previous:{title:"Optimal Path Finding Questions",permalink:"/docs/Patterns/DynamicProgramming/Coordinate/OptimalPathFinding/index"},next:{title:"LC310. Minimum Height Trees",permalink:"/docs/QuestionBank/Leetcode/LC310"}},u=[{value:"Power of 2",id:"power-of-2",children:[]},{value:"Log Base of 2",id:"log-base-of-2",children:[]},{value:"Count Ones In Binary Representation",id:"count-ones-in-binary-representation",children:[]},{value:"References:",id:"references",children:[]}],l={toc:u};function s(e){var n=e.components,t=Object(o.a)(e,["components"]);return Object(i.b)("wrapper",Object(r.a)({},l,t,{components:n,mdxType:"MDXLayout"}),Object(i.b)("h2",{id:"power-of-2"},"Power of 2"),Object(i.b)("pre",null,Object(i.b)("code",Object(r.a)({parentName:"pre"},{}),"1 << x === 2^x\n")),Object(i.b)("h2",{id:"log-base-of-2"},"Log Base of 2"),Object(i.b)("pre",null,Object(i.b)("code",Object(r.a)({parentName:"pre"},{}),"# log(a) base b = log(a)/log(b)\n32 >> 5 === log(32)/log(2) \n")),Object(i.b)("h2",{id:"count-ones-in-binary-representation"},"Count Ones In Binary Representation"),Object(i.b)("ul",null,Object(i.b)("li",{parentName:"ul"},Object(i.b)("inlineCode",{parentName:"li"},"n&(n-1)")," rule: is used when you want to quickly count how many ",Object(i.b)("inlineCode",{parentName:"li"},"1s")," in your binary number, every-time you do ",Object(i.b)("inlineCode",{parentName:"li"},"n&(n-1)"),", a ",Object(i.b)("inlineCode",{parentName:"li"},"1")," in your binary form will be removed:")),Object(i.b)("pre",null,Object(i.b)("code",Object(r.a)({parentName:"pre"},{className:"language-java"}),"// first run\nn = 23 // (10111)\nnMinusOne = n - 1 // === 22 (10110)\nn = n & nMinusOne // === 22 (10111 & 10110 = 10110)\n// second run\nnMinusOne = 22 - 1 // == 21 (10101)\nn = n & nMinusOne // == 20 (10110 & 10101 = 10101)\n// third run\nnMinusOne = 20 - 1 // == 19 (10011)\nn = n & nMinusOne // == 16 (10101 & 10011 = 10000)\n// fourth run\nnMinusOne = 16 - 1 // == 15 (01111)\nn = n & nMinusOne // == 0 (10000 & 01111 = 00000)\n// after 4 times, n becomes 0; hence there are 4 1s in your original binary form of int 23\n")),Object(i.b)("ul",null,Object(i.b)("li",{parentName:"ul"},"in short:")),Object(i.b)("pre",null,Object(i.b)("code",Object(r.a)({parentName:"pre"},{className:"language-java"}),"int count_one(int n) {\n    while(n) {\n        n = n&(n-1);\n        count++;\n    }\n    return count;\n}\n")),Object(i.b)("h2",{id:"references"},"References:"),Object(i.b)("ul",null,Object(i.b)("li",{parentName:"ul"},Object(i.b)("a",Object(r.a)({parentName:"li"},{href:"https://leetcode.com/problems/sum-of-two-integers/discuss/84278/A-summary%3A-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently"}),"https://leetcode.com/problems/sum-of-two-integers/discuss/84278/A-summary%3A-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently"))))}s.isMDXComponent=!0},147:function(e,n,t){"use strict";function r(){return(r=Object.assign||function(e){for(var n=1;n<arguments.length;n++){var t=arguments[n];for(var r in t)Object.prototype.hasOwnProperty.call(t,r)&&(e[r]=t[r])}return e}).apply(this,arguments)}t.d(n,"a",(function(){return r}))},148:function(e,n,t){"use strict";t.d(n,"a",(function(){return p})),t.d(n,"b",(function(){return d}));var r=t(0),o=t.n(r);function i(e,n,t){return n in e?Object.defineProperty(e,n,{value:t,enumerable:!0,configurable:!0,writable:!0}):e[n]=t,e}function a(e,n){var t=Object.keys(e);if(Object.getOwnPropertySymbols){var r=Object.getOwnPropertySymbols(e);n&&(r=r.filter((function(n){return Object.getOwnPropertyDescriptor(e,n).enumerable}))),t.push.apply(t,r)}return t}function c(e){for(var n=1;n<arguments.length;n++){var t=null!=arguments[n]?arguments[n]:{};n%2?a(Object(t),!0).forEach((function(n){i(e,n,t[n])})):Object.getOwnPropertyDescriptors?Object.defineProperties(e,Object.getOwnPropertyDescriptors(t)):a(Object(t)).forEach((function(n){Object.defineProperty(e,n,Object.getOwnPropertyDescriptor(t,n))}))}return e}function u(e,n){if(null==e)return{};var t,r,o=function(e,n){if(null==e)return{};var t,r,o={},i=Object.keys(e);for(r=0;r<i.length;r++)t=i[r],n.indexOf(t)>=0||(o[t]=e[t]);return o}(e,n);if(Object.getOwnPropertySymbols){var i=Object.getOwnPropertySymbols(e);for(r=0;r<i.length;r++)t=i[r],n.indexOf(t)>=0||Object.prototype.propertyIsEnumerable.call(e,t)&&(o[t]=e[t])}return o}var l=o.a.createContext({}),s=function(e){var n=o.a.useContext(l),t=n;return e&&(t="function"==typeof e?e(n):c(c({},n),e)),t},p=function(e){var n=s(e.components);return o.a.createElement(l.Provider,{value:n},e.children)},b={inlineCode:"code",wrapper:function(e){var n=e.children;return o.a.createElement(o.a.Fragment,{},n)}},f=o.a.forwardRef((function(e,n){var t=e.components,r=e.mdxType,i=e.originalType,a=e.parentName,l=u(e,["components","mdxType","originalType","parentName"]),p=s(t),f=r,d=p["".concat(a,".").concat(f)]||p[f]||b[f]||i;return t?o.a.createElement(d,c(c({ref:n},l),{},{components:t})):o.a.createElement(d,c({ref:n},l))}));function d(e,n){var t=arguments,r=n&&n.mdxType;if("string"==typeof e||r){var i=t.length,a=new Array(i);a[0]=f;var c={};for(var u in n)hasOwnProperty.call(n,u)&&(c[u]=n[u]);c.originalType=e,c.mdxType="string"==typeof e?e:r,a[1]=c;for(var l=2;l<i;l++)a[l]=t[l];return o.a.createElement.apply(null,a)}return o.a.createElement.apply(null,t)}f.displayName="MDXCreateElement"},149:function(e,n,t){"use strict";function r(e,n){if(null==e)return{};var t,r,o={},i=Object.keys(e);for(r=0;r<i.length;r++)t=i[r],n.indexOf(t)>=0||(o[t]=e[t]);return o}t.d(n,"a",(function(){return r}))}}]);