Skip to main content

Posts

BITWISE NOT

Bitwise NOT The  NOT  bitwise operation inverts bits. A  0 0  becomes a  1 1 . A  1 1  becomes a  0 0 . The NOT operator is often written as a  tilde character  (" ~ "): ~ 0000 0101 = 1111 1010 C C# C++ Java JavaScript Objective-C PHP Python 2.7 Python 3.6 Ruby Swift When numbers are printed in base-10, the result of a NOT operation can be surprising. In particular, positive numbers can become negative and negative numbers can become positive. For example: ~ 5 // gives -6 // At the bit level: // ~ 0000 0101 (5) // = 1111 1010 (-6) C C# C++ Java JavaScript Objective-C PHP Python 2.7 Python 3.6 Ruby Swift This is because  numbers are (usually) represented using two's complement, where the leftmost bit is actually negative . So flipping the leftmost bit usually flips the sign of the number. See also: Binary Numbers Bitwise AND Bitwise OR Bitwise XOR (eXclusive OR) Bit Shifting
Recent posts

BIT SHIFTING

Bit Shifting A  bit shift  moves each digit in a number's binary representation left or right. There are three main types of shifts: Left Shifts When shifting left, the most-significant bit is lost, and a  0 0  bit is inserted on the other end. The left shift operator is usually written as " << ". 0010 << 1 → 0100 0010 << 2 → 1000 A single left shift multiplies a binary number by 2: 0010 << 1 → 0100 0010 is 2 0100 is 4 Logical Right Shifts When shifting right with a  logical right shift , the least-significant bit is lost and a  0 0  is inserted on the other end. 1011 >>> 1 → 0101 1011 >>> 3 → 0001 For positive numbers, a single logical right shift divides a number by 2, throwing out any remainders. 0101 >>> 1 → 0010 0101 is 5 0010 is 2 Arithmetic Right Shifts When shifting right with an  arithmetic right shift , the least-significant bit is lost and the most-significant bit is  copied . Language

BITWISE XOR

Bitwise XOR (eXclusive OR) The  XOR  operation (or  exclusive or ) takes two bits and returns  1 1  if  exactly one  of the bits is  1 1 . Otherwise, it returns  0 0 . 1 ^ 1 → 0 1 ^ 0 → 1 0 ^ 1 → 1 0 ^ 0 → 0 Think of it like a bag of chips where only one hand can fit in at a time. If no one reaches for chips, no one gets chips, and if both people reach for chips, they can't fit and no one gets chips either! When performing XOR on two integers, the XOR operation is calculated on each pair of bits (the two bits at the same index in each number). 5 ^ 6 // gives 3 // At the bit level: // 0101 (5) // ^ 0110 (6) // = 0011 (3) C C# C++ Java JavaScript Objective-C PHP Python 2.7 Python 3.6 Ruby Swift See also: Binary Numbers Bitwise AND Bitwise OR Bitwise NOT Bit Shifting

BITWISE OR

Bitwise OR The  OR  operation takes two bits and returns  1 1  if  either  of the bits are  1 1 . Otherwise, it returns  0 0 . 1 | 1 → 1 1 | 0 → 1 0 | 1 → 1 0 | 0 → 0 Think of it like a bucket with two holes in it. If  both  holes are closed, no water comes out. If  either  hole is open,  or if both  are open, water comes out. When performing OR on two integers, the OR operation is calculated on each pair of bits (the two bits at the same index in each number). 5 | 6 // gives 7 // At the bit level: // 0101 (5) // | 0110 (6) // = 0111 (7) C C# C++ Java JavaScript Objective-C PHP Python 2.7 Python 3.6 Ruby Swift See also: Binary Numbers Bitwise AND Bitwise NOT Bitwise XOR (eXclusive OR) Bit Shifting

BITWISE AND

Bitwise AND The  AND  operation takes two bits and returns  1 1  if  both  bits are  1 1 . Otherwise, it returns  0 0 . 1 & 1 → 1 1 & 0 → 0 0 & 1 → 0 0 & 0 → 0 Think of it like a hose with two knobs.  Both  knobs must be set to on for water to come out. When performing AND on two integers, the AND operation is calculated on each pair of bits (the two bits at the same index in each number). 5 & 6 // gives 4 // at the bit level: // 0101 (5) // & 0110 (6) // = 0100 (4) C C# C++ Java JavaScript Objective-C PHP Python 2.7 Python 3.6 Ruby Swift See also: Binary Numbers Bitwise OR Bitwise NOT Bitwise XOR (eXclusive OR) Bit Shifting

STACK

Stack Data Structure Quick reference Worst Case space O(n) O ( n ) push O(1) O ( 1 ) pop O(1) O ( 1 ) peek O(1) O ( 1 ) A  stack  stores items in a last-in, first-out (LIFO) order. Picture a pile of dirty plates in your sink. As you add more plates, you bury the old ones further down. When you take a plate off the top to wash it, you're taking the last plate you put in. "Last in, first out." Strengths: Fast operations . All stack operations take  O(1) O ( 1 )  time. Uses: The call stack  is a stack that tracks function calls in a program. When a function returns, which function do we "pop" back to? The last one that "pushed" a function call. Depth-first search  uses a stack (sometimes the call stack) to keep track of which nodes to visit next. String parsing —stacks turn out to be useful for  several types of string parsing . Implementation You can implement a stack with either a  linked list  or a  dynamic array —they both work pretty well: Stack Push