Matching Names With Corresponding 32 Bit Unsigned Integers
Solution 1:
If you read the problem carefully, this is a question about "how many identical bits do two 32 bit numbers have). You have to examine the number in binary form (where you can look at each bit) and compare bits between the numbers that represent each person's characteristics.
So, one person's number might be represented in bary as
01001101110011010011010100101111
and another as
01111100010011010011010100010111
To see how well they match, you have to see how many bits have the same value where the bit in the same corresponding position is both 0 or both 1. Add one to the matching score for each bit that has the same value.
Since this is some sort of learning exercise, I won't just hand you the code, but will point you to a reference on manipulating bits in Javascript.
As it turns out, there are multiple phases to this problem:
- Compare the mask number for two people and generate a match score.
- For all possible user combinations, compute all match scores.
- Find the highest match score, add them to the final results, remove them from all the match scores you have so far and find the next highest match. Repeat until there are 0 or 1 people left.
Output from my solution (which has not yet been linked so the OP can work the problem themselves):
Visually in Binary
00000110111010110011001011101001 Danniel
10001010000110001110011010011001 Bowman
10000010010100010000010010000110 Cleveland
10011110101011101000101100000111 Marinda
11001010010001110111100001111010 Viviana
All Comparisons (sorted)
Bowman,Cleveland:19
Danniel,Viviana:17
Danniel,Bowman:16
Cleveland,Viviana:16
Danniel,Cleveland:15
Danniel,Marinda:15
Bowman,Marinda:15
Bowman,Viviana:15
Cleveland,Marinda:14
Marinda,Viviana:12
Best Matches
Bowman,Cleveland: 19
Danniel,Viviana: 17
Here's a hint for comparing if a given bit is the same in two numbers:
var bitmask = 1; // start with lowest bitvar num1 = 116077289;
var num2 = 2316887705;
if ((num1 & bitmask) === (num2 & bitmask)) {
// the bit represented by bitmask is the same in both numbers
}
Next hint: If bitmask is 2, then you're comparing the second bit. If bitmask is 4, you're comparing the third bit, 8 then the fourth bit, 16, the fifth bit and so on up to the 32nd bit. Add a counter and you can count the bits that match.
Here's a working solution:
// function used to make display prettierfunctionzeroPadLeft(str, len) {
while (str.length < len) {
str = "0" + str;
}
return str;
}
functioncompareBits(num1, num2) {
// score is the number of matching bitsvar score = 0;
// start with first bitvar mask = 1;
// create rotating mask to individually compare each of the lowest 32 bitsfor (var i = 0; i < 32; i++) {
// if this bit has the same value, increase the scoreif ((num1 & mask) === (num2 & mask)) {
++score;
}
// advance mask to next bit with shift left operator
mask = mask << 1;
}
return score;
}
// input datavar data = [
{name:"Danniel", value:116077289},
{name:"Bowman", value:2316887705},
{name:"Cleveland", value:2186347654},
{name:"Marinda", value:2662238982},
{name:"Viviana", value:3393681530}
];
// show the starting data in binary so we can see a visual representation of the actual bitslog("<b>Visually in Binary</b>");
data.forEach(function (item) {
log(zeroPadLeft(item.value.toString(2), 32) + " " + item.name);
});
// record the score of all possible combinations in the scores array of objectslog("<hr>");
log("<b>All Comparisons</b>");
var scores = [];
for (var j = 0; j < data.length; j++) {
for (var k = j + 1; k < data.length; k++) {
var score = compareBits(data[j].value, data[k].value);
// record the score and two names as an object inserted into an array
scores.push({
name1: data[j].name,
name2: data[k].name,
score: score
})
}
}
// sort by best score to make it easier to find the highest score
scores.sort(function (a, b) {
return b.score - a.score;
});
// output sorted scores so we can see them visually
scores.forEach(function (item) {
log(item.name1 + "," + item.name2 + ":" + item.score);
});
// now find the top scores with no person repeatedlog("<hr>");
log("<b>Best Matches</b>");
// namesUsed keeps track of which names have already found a high score so we don't use them againvar namesUsed = {};
while (scores.length > 0) {
var bestItem = scores.shift();
// if either of these names has already been used, then skip this scoreif (namesUsed[bestItem.name1] || namesUsed[bestItem.name2]) {
continue;
}
log(bestItem.name1 + "," + bestItem.name2 + ": " + bestItem.score);
namesUsed[bestItem.name1] = true;
namesUsed[bestItem.name2] = true;
}body {font-family: "Courier New";}<scriptsrc="http://files.the-friend-family.com/log.js"></script>Explanation of comparing bits
The key part is counting the bits that are the same in two numbers:
functioncompareBits(num1, num2) {
// score is the number of matching bitsvar score = 0;
// start with first bitvar mask = 1;
// create rotating mask to individually compare each of the lowest 32 bitsfor (var i = 0; i < 32; i++) {
// if this bit has the same value, increase the scoreif ((num1 & mask) === (num2 & mask)) {
++score;
}
// advance mask to next bit with shift left operator
mask = mask << 1;
}
return score;
}
This is what I think is the simplest to understand implementation (not the fastest). Basically what it does is define a mask number with an initial value of 1. When we logically AND the mask number with each of our values, we isolate a single bit in each number. We can then compare that remaining single bit to see if they are equal. If so, increase our score. Then, shift the mask left by one place so we can look at the next bit. Repeat that 32 times and we've compared each of the 32 bits, counting how many have the same value.
If you want to see how obtuse bit manipulation can get, here's a pretty fast algorithm called the Hamming weight implementation:
functioncountSimilarBitsHamming(num1, num2) {
// xor sets a bit to 0 if both are the same and 1 if different// so if we xor and then negate, we get bits that are the samevar sameBits = ((~(num1 ^ num2)) & 0xFFFFFFFF) >>> 0;
sameBits = sameBits - ((sameBits >> 1) & 0x55555555);
sameBits = (sameBits & 0x33333333) + ((sameBits >> 2) & 0x33333333);
return (((sameBits + (sameBits >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
Here's an even slower implementation, but the bit counting part is a simple string count:
functioncountBitsString(num1, num2) {
// xor sets a bit to 0 if both are the same and 1 if different// so if we xor and then negate, we get bits that are the samevar sameBits = ((~(num1 ^ num2)) & 0xFFFFFFFF) >>> 0;
var str = sameBits.toString(2).replace(/0/g, "");
return str.length;
}
Steps:
- num1 XOR num2 - This generates a result where a bit is set to
0if both corresponding bits in num1 and num2 had the same value or1if they were different values. - That XOR value is the inverse of what we want so we negate it with the
~operator. Now we have a1wherever the two numbers had equal bits. - Because there are more than 32 bits in the negated value, we and it with the max 32-bit value to zero out the higher bits.
- Then because Javascript only deals with signed values, but we want unsigned values, we use a trick of doing a zero fill right shift, but with a
0shift value>>> 0and this will clear the sign bit. - Now there is a list of matching bits.
- Then, a really simple way to count them is to convert to string represeantation of binary and remove the zeroes. All that will be left is the
1s in the string so just see how long the string is and that's how many1s where in the string.
Solution 2:
"Bit" is short for "binary digit". Therefore, a 32-bit integer is an integer that can be represented using 32 binary digits. An "unsigned" integer cannot be negative, and so it is stored using plain binary instead of using two's complement.
In binary, the input might make more sense.
Danniel 00000110111010110011001011101001
Bowman 10001010000110001110011010011001
Cleveland 10000010010100010000010010000110
Marinda 10011110101011101000101100000111
Viviana 11001010010001110111100001111010
According to the problem, compatibility is measured by the number of identical bits. Therefore, you can use the bitwise operator &. The bitwise AND combines two numbers by comparing bit by bit. If both bits are the same it will put a 1 in the result. If both bits are different, it will put a 0 in the result.
For example, here's how & would compare Danniel with Bowman.
Danniel 00000110111010110011001011101001
Bowman 10001010000110001110011010011001
Result: 01110011000011000010101110001111To find the most compatible couple, find the couple whose & results in the most1s.
To find the least compatible couple, find the couple whose & results in the fewest1s.
Solution 3:
AFTER 5 HOURS OF HITTING MY HEAD
functioncompareBit(num1,num2)
{
var mask = 1;
var count = 0;
for(var i = 0; i<32;i++)
{
if((num1&mask) === (num2&mask))
{
++count;
}
mask = mask << 1;
}
return count;
}
var obj = [];
var number = prompt("Enter how many names and id's you will put");
for(var i = 0 ; i<number ; i++)
{
query = prompt("Enter name then id, you must put one space in between");
query_result = query.split(" ");
obj.push({name:query_result[0],value:query_result[1]});
}
var scores = [];
for (var a = 0 ; a<obj.length ; a++){
for(var b = a+1 ; b<obj.length ; b++){
var score = compareBit(obj[a].value,obj[b].value);
scores.push({name1:obj[a].name,name2:obj[b].name,score:score})
}
}
var max = scores.reduce(function(prev,current){
return (prev.score > current.score) ? prev : current;
});
var min = scores.reduce(function(prev,current){
return (prev.score < current.score) ? prev : current;
});
console.log(max.name1+ " " + max.name2);
console.log(min.name1+ " " + min.name2);
Post a Comment for "Matching Names With Corresponding 32 Bit Unsigned Integers"