1

I am trying to perform some bitwise operations on a given key for a hash table program. The methods that I am trying to figure out are folding, mid-square, truncation, and radix. I am not expecting anyone to give me the direct answer, but help send me in the right direction. I cannot find any correspondence or help online that refers to this, or any algorithms that may help. I have a bitwise program that shows some of the operations on binary numbers, such as shifting, XOR, OR, AND< and so on. What I am not understanding is how to select only one portion of a 32 bit binary number, such as in mid-square, where you would select the middle four bits, and use just those in the operation. I have tried several things, but the following is what I have ended up with. I think the mid-square works (not sure though), but only seems to work on large integers. The folding and truncation definitely are not working. I haven't even attempted the radix method. Any help, guidance, or referring me to the appropriate documentation that would be most helpful would be great.

int location = 0;

    if(hFunction == FOLDING){
        location = (key & 0xff000000) >> 2;
        location = location + ((key & 0x00ff0000) >> 2);
        location = location + ((key & 0x0000ff00) >> 2);
        location = location + ((key & 0x000000ff) >> 2);
        cout << "\n" << location << "\n";   // for debuggin
    }
    else if(hFunction == MIDSQUARE){
        location = ((key * key) & 0x00ffff00) >> 2;
        cout << "\n" << location << "\n";   // for debuggin
    }
    else if(hFunction == TRUNCATION){
        location = (key & 0x000ffff0) << 1;
        cout << "\n" << location << "\n";   // for debugging
    }
    else if(hFunction == RADIX){
        return(0);
    }

    // Divsion Method
    location %= tableSize;
    keys++;

    return(location);

EDIT (Revisions): Ok, here are some revisions I have made. I don't know if any of these are right, but let me know what can be changed, better optimized, and is totally wrong. I get output with all four methods, but whether or not is is all right, I don't know yet. I haven't thoroughly examined each.

REVISED CODE:

int location = 0;

    // splits key and adds the sections together - discards remainder
    if(hFunction == FOLDING){
        while (key != 0){
            location = location + key % 100;
            key = key / 100;
        }
        //cout << location << "\n";         // for debugging
    }
    // squares the key and then shifts right 2 spaces
    else if(hFunction == MIDSQUARE){
        location = ((key * key) & 0x00ffff00) << 2;
        //cout << location << "\n";         // for debugging
    }
    // mods the key by 100, then divides by 10, splitting it into different digits, 
    // then adds those digits together
    else if(hFunction == TRUNCATION){
        while (key != 0){
            location = location + key % 100;
            key = key / 10;
        }
        //cout << location << "\n";         // for debugging
    }
    // converts the key to a character array while also taking all digits of the key and 
    // multiplying them by base 5, then converts back to an integer
    else if(hFunction == RADIX){
        char buffer[33];
        _itoa_s(key, buffer, 5);
        //cout << key;                      // for debugging
        //system("pause");                  // for debugging
        location = atoi(buffer);
        //cout << location << "\n";         // for debugging
    }

    // Divsion Method
    location %= tableSize;
    keys++;                                 // counts the keys per hash table

    return(location);
4

0 回答 0