The program will perform the following:

Print CS12 to the screen

Query the user to enter a Quadword in ascii format:

123456abcd

Print the register containing the quad word

Print out a binary search sequence finding the number

Print out a register containing the value of the number if itterations

Sample c00000000000

This example

0xC00000000000

Takes 0x12 iterations

This example

0x2000000000000000

Takes 0x3 iterations

Your output should match examples, and work for varous values from 0x0 to 0xFFFFFFFFFFFFFF

main.cpp

//

// main.cpp

/

#include

using namespace std;

int main(int argc, const char * argv[]) {

unsigned long int number = 0x0;

unsigned long int domain = 0x8000000000000000; // 1/2 of 64 bit

max number 0xffffffffffffffff

unsigned long int guess = 0 + domain; // first guess is the

same as the domain

unsigned int count = 1; // first guess

// allow stdin to take 0x prefix

std::cin.unsetf(std::ios::dec);

std::cin.unsetf(std::ios::hex);

// display the prompt

cout

cout

cin >> number;

cout

cout

// check to see if the number is greater, less or equal

while (guess != number) // we guessed it so were done

{

// because we made a guess our domain will reduce in half

domain = domain>>1; // divide the domain in half

if (guess > number) // we need to guess a smaller number

{

guess -= domain; // guess a smaller number by subtracting

}

else

{

guess += domain; // guess a larger number by adding

}

count++;

cout

}

// output the number of guesses

cout

return 0;

}

Algorithm

output: CS12 output: Enter up to a quadword in hex: example:ABCDEF12345678 accept a quadword from the user into rax display the quadword returned in the register rax

;; rax now has the value were searching for ;; binary seach for this value ;; start the domain value in the middle 0x8000000000000000 (perhaps set a register or memory value to this) ;; the first guess with be the domain value 0x8000000000000000 ;; additional guesses will be half the previous domain added, or subtracted as shown below

guess print out the guess increment the counter reduce the domain value by one bit, or half its current value (this can be done with a shift, or div operation) compare the guess with the value input by the user if this is correct go to label match if the guess is to low go to label greater if the guess is to high to to label lower

match: print out the number of guesses (counter) goto exit

greater: guess a larger number by adding the domain value to the number go to guess

lower: guess a smaller number by subtracting the domain value to the number go to guess

The domain is the number of remaining numbers we need to search.

Initially it is the full 64 bits 0x0 to 0xFFFFFFFFFFFFFFFF Then we take the mid point 0x8000000000000000 and compare to the number input This divides the problem in half if the number is greater we only need look at numbers 0x8000000000000001 to 0xFFFFFFFFFFFFFFFF if the number is lesser we only need look at numbers 0x0 to 0x8000000000000000 The domain will reduce by a factor of 2 each time because were splitting the problem in half so each guess iteration we can either divide the domain by 2, or shift the domain by one bit to the right

Look at the image below, the domain is represented by the horizontal lines, note how it gets reduced in half for each iteration.

ubuntuoubuntu:-/CS12-Labs/control CS12 Enter up to a quadword in hex: example:ABCDEF12345678 0x8000000000000000 0xc000000000000000 ex0000000000000002 ubuntu@ubuntu:-/CS12-Labs/controls ubuntuoubuntu:-/CS12-Labs/control CS12 Enter up to a quadword in hex: example:ABCDEF12345678 0x8000000000000000 0xc000000000000000 ex0000000000000002 ubuntu@ubuntu:-/CS12-Labs/controls