0

this is a test program to try to get my bitwise shift operations to work. I am hoping to add this to my cache simulator program, but I can't even get this part to work. My plan is to use bit shift (<<) and (>>) to isolate parts of a given memory address (tag, set, word, etc.) but it seems that in shifting the bits back right, it is filling with the values which were previously there, rather than with 0's. Here is the program first.

#include<iostream>
#include <cmath>

struct Address{
    unsigned int tag;
    unsigned int r;
    unsigned int word;
};

int main(){
    unsigned int tempAddress = 27; //0011011
    int ramSize = 128;
    int cacheSize = 64;
    int blockSize = 8;

    int cacheLines = cacheSize / blockSize;

    int addressLength = log(ramSize)/log(2);
    int wordBits = log(blockSize)/log(2);
    int rBits = log(cacheLines)/log(2);
    int tagBits = addressLength - (wordBits + rBits);

    struct Address address;

    address.tag = tempAddress >> (rBits + wordBits);
    address.r = tempAddress << (tagBits) >> (tagBits + wordBits);
    address.word = tempAddress << (rBits + tagBits) >> (rBits + tagBits);

    std::cout << "tag is: " << address.tag << "\n";
    std::cout << "r is: " << address.r << "\n";
    std::cout << "word is: " << address.word << "\n";


}

I've found that when my tempAddress is [0-7] it works fine because binary 7 only affects the first 3 bits. Similarly, when it is [8-63], tag and r are correct because 63 affects the first 6 bits. Upon testing many addresses, I've found that when shifting right after shifting left, the bits are being replaced with what they were before, rather than with 0s as I think they should be.

(r is the part that is in the middle. I am calling it r because in direct mapping it is called line, and in set-associative mapping it is called set)

EDIT:

As someone pointed out, expected and produced outcome would be helpful. I'd first like to keep the cache size, ram size, and block size constant, and only change the address.

So, given tempAddress = 27(0011011 in binary), word should be 011 (first 3 bits), r should be 011 (next 3), and set should be 0 (remaining bits). Output is this:

tag is: 0
r is: 3
word is: 27

I've found this to be the trend if every address between 0 and 63(inclusive) that tag and r are correct, but word is equal to address.

Now, for address = 65(1000001) Expected:

tag is: 1
r is: 0
word is: 1

Output:

tag is: 1
r is: 8
word is: 65

With these ram, cache, and block sizes, to find r, I am left shifting 1 time, and right shifting 4 times. To find word, I am left shifting 4 times, then right shifting 4 times. As I understand it, when left shifting the bits on the right are filled with 0, and when right shifting an unsigned integer, the bits on the left are filled with 0. My thought was that if I left shift until I only have the bits I need, then right shift them back to the first bits, I will have the correct values. However, consistent throughout numerous addresses, after left shifting then right shifting, the places that had 1s still do. That is why word is always equal to address, because I am shifting 4 bits both left then right. And r is always equal to the 7 bits shifted right 3 times (because I go left 1 then right 4). Am I misunderstanding how bitwise shifting works?

hobbsdevon
  • 23
  • 4
  • If you have full confidence in your analysis (the "I've found that" parts), then by all means use that to solve your problem. However, if your analysis falls short, it would be better to explicitly give the expected and actual output. (Even if that can be guessed from your conjectures, how much work do you want to dump on the people *volunteering* to help?) Start with the hard facts and pose your question before moving into your context ("cache simulator program") and analysis. Your code would probably fit well after the question mark and before the context. – JaMiT Jun 09 '21 at 02:28
  • You might get a better understanding of your own question if you spend some more time on your [mre] (note: it's not bad, but room to improve). Currently, the code bears many signs of its "cache simulator" origin. Think abstractly about your operations. Pick one operation that does not perform as expected and focus on that. Drop parts extraneous to that operation. Name your variables for how they relate to that operation instead of how they relate to memory addressing. Your `main` function might reduce to a few lines to initialize variables, one line with the operation, and one line for output. – JaMiT Jun 09 '21 at 02:34
  • 1
    Consider what values `addressLength` and your various `Bits` values have, what values they should have (because floating point math can be slightly imprecise, the calculated value may not be what you expect), and the resulting value for `tagBits` (which could be negative). – 1201ProgramAlarm Jun 09 '21 at 02:51
  • @1201ProgramAlarm During testing I was printing the values of 'addressLength' and the 3 'Bits' values. I removed this part because they were correct 100% of the time. Thank you. – hobbsdevon Jun 09 '21 at 03:14
  • I think it could be that though my example has an address length of 7 bits, the computer is still storing 16/32 bits because it's an integer. If anyone has suggestions on how to get around this that would be much appreciated. The solutions always seem so obvious once you think of them. – hobbsdevon Jun 09 '21 at 03:37
  • 1
    Rather than all this shifting, have you considered using masking (bitwise `&` operator)? – 1201ProgramAlarm Jun 09 '21 at 03:37
  • @1201ProgramAlarm I have. I thought that would be a possibility but couldn't figure out how. I'm familiar with bitwise &, but I've never heard the term masking. I'll look for some good information about it. Thank you for the help. – hobbsdevon Jun 09 '21 at 03:43
  • Bit masking is simply if you have an integral value and apply `& mask` to isolate certain bits i.e. "mask out" everything else. Thereby all bits of the integral value are cleared which are 0 in `mask`, i.e. only bits of the integral value are kept which are 1 in `mask`. – Scheff's Cat Jun 09 '21 at 05:41
  • 1
    _but it seems that in shifting the bits back right, it is filling with the values which were previously there, rather than with 0's._ This is called [sign extension](https://stackoverflow.com/a/15730750/7478597) and happens if you do right shift with signed integrals. Use unsigned integrals instead. Then you won't have sign extension. – Scheff's Cat Jun 09 '21 at 05:46

0 Answers0