Check if a string has all unique characters
public boolean isUnique(String s) { if (s == null) throw new NullPointerException("Null string!"); if (s.length() == 0) return true; int check = 0; for (int i = 0; i < s.length(); i++) { int val = Character.getNumericValue(s.charAt(i)); if ((check & (1 << val)) > 0) return false; check |= (1 << val); } return true; }
Insert bits
You are given two 32-bit numbers, N and M, and two bit positions, i and j.Write a method to set all bits between i and j in N equal to M (e.g., M becomes a substring of N located at i and starting at j).
Set all positions after j to zero
Set all positions after i back to 1
get the mask where all bits between i to j is cleared
put m into n from ith position
public int insertBitnumber(int m, int n, int posi, int posj) { //32 bit of 1s == -1; int max = ~0; /* e.g., posj = 3 * 1 << posj = 1000 * (1 << posj) - 1 = 111 * max - that will leave all bits after j = 0; */ int left = max - ((1 << posj) - 1); int right = (1 << posi) - 1; //this operation will leave all positions between posi and posj equals zero int mask = left | right; //mask & n will clear all bits between i and j in n // then we put m in those positions return (mask & n) | (m << posi); }
Decimal To Binary
Given a (decimal - e.g.3.72) number that is passed in as a string, print the binary representation.If the number can not be represented accurately in binary, print “ERROR” .
Given an binary integer, we know that 1001 = 1 * 2^ 3 + 0 * 2 ^ 2 + 0 * 2 ^ 1 + 1 * 2^0 = 9. So if we keep doing mod operation and divide the number by 2, we can get the binary representation of the integer.
Analogously, 0.101 = 1 * (1/2)^1 + 0 * (1/2)^2 + 1 * (1/2)^3 = 0.625. Thus if we multiply the number by 2, we get 1 * (1/2)^0 + 0 * (1/2)^1 + 1 * (1/2)^2 = 1.25(10) = 1.01(2). So if the result is greater than 1, we know that there should be 1 follows "." in the decimal part. We can do the same operation for every digit.
public class DecimalToBinary { public String decimalToBinary (String s) { if (s == null) throw new NullPointerException("Null string"); int intPart = Integer.parseInt(s.substring(0, s.indexOf('.'))); double deciPart = Double.parseDouble(s.substring(s.indexOf('.'))); String rst = ""; while (intPart > 0) { rst = String.valueOf(intPart % 2) + rst; intPart >>= 1; } rst += "."; String decim = ""; while (deciPart > 0) { if (decim.length() > 32) { return "Error"; } if (deciPart == 1) { decim += "1"; break; } double d = deciPart * 2; if (d >= 1) { decim += "1"; deciPart = d - 1; } else { decim += "0"; deciPart = d; } } return rst + decim; } }
Next Largest and Smallest number that has the same number of 1 bits
Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation.
Ok, this is interesting. So basically, given a binary number, 11100110, if we want to find the next largest one that has the same number of 1 bits, we first switch the first 0 to 1, which gives us 11101110, then we switch the next 1 after that 0 to 0, and results in 11101010. Since we want the next largest, we would want to shift all the 1s after that to the most right side, and the result is: 11101001, yep, here is the solution.
The next smallest number is similar. Reversely, we switch the first 1 to 0 and the next 0 to 1. Using another example 110011 would result in 101011, and shifts, and the answer is: 101110.
public class NextBitNumber { private int setBit(int n, int index, boolean toOne) { int rst; if (toOne) rst = n | (1 << index); else { int mask = ~ (1 << index); rst = n & mask; } return rst; } private boolean getBit(int n, int index) { return (n & (1 << index)) > 0; } public int nextLargest(int n) { if (n <= 0) return -1; int index = 0; int countOnes = 0; while (!getBit(n, index)) index++; while(getBit(n, index)) { index++; countOnes++; } n = setBit(n, index, true); index--; n = setBit(n, index, false); countOnes--; index--; for (int i = index; i > index - countOnes; i--) n = setBit(n, i, false); for (int i = 0; i < countOnes; i++) n = setBit(n, i, true); return n; } public int nextSmallest(int n) { if (n <= 0) return -1; int index = 0; int countZeros = 0; while (getBit(n, index)) { index++; } while (!getBit(n, index)) { index++; countZeros++; } n = setBit(n, index, false); index--; n = setBit(n, index, true); index--; countZeros--; for (int i = index; i > index - countZeros; i--) n = setBit(n, i, true); for (int i = 0; i < countZeros; i++) n = setBit(n, i, false); return n; } }
What does (n & (n - 1)) == 0 used for?
Check if n == 0 or power of 2!
For example, 100 and 11;
Bits needed to convert a number to another number
Write a function to determine the number of bits required to convert integer A to integer B.
Input: 31, 14
Output: 2
Count the number of different bits in a number by using XOR.
public class BitsNeededToConvert { public int bitsNeeded(int a, int b) { if (a == b) return 0; int count = 0; for (int c = a ^ b; c >= 0; c = c>> 1) { count += c & 1; } return count; } }
Something about Hexadecimal
In Unix shells, and C programming language:
prefix 0x for numeric constants represented in hex. e.g., 0x5A3 (144310).
Character and string constants may express characters codes in hexadecimal with the prefix \x followed by two hex digits: \x1B (Esc control character)
Unicode standard:
A character value is represented with U+ followed by the hex value, e.g., U+20AC (euro sign)
Convert hexadecimal to binary
Swap odd and even bits in a number
Write a program to swap odd and even bits in an integer with as few instructions as possible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc).
shift all odd bits left for 1 position and shift all even bits right for 1 position
public class SwapBits { public int swapBits (int n) { //0xaaaaaaaa = 10101010...10 // 0x55555555 = 1010101...01 return (n & 0xaaaaaaaa) >> 1 | (n & 0x55555555) << 1; } }
No comments:
Post a Comment