Masm32 SDK description, downloads and other helpful links
Message to All Guests
NB: Posting URL's See here: Posted URL Change

Main Menu

A collection of programming problems

Started by jj2007, December 23, 2022, 12:55:38 AM

Previous topic - Next topic


OK, I read the post where David Maynard threw down his gauntlet (made quite a bang) and explained the bit-vector thing. Which is dead simple: 1 million bits, each representing an integer depending on its position. Even I can understand that.

So what a guy would need in order to access the ith bit in this "vector" are two things: a pointer to a byte and a bit mask to isolate the bit. Here's my take on how to do that:

MOV ECX, EAX ;Save original i
SHR EAX, 3 ;Divide by 8
MOV EDX, EAX ;Pointer to the right byte
SHL EAX, 3 ;Back to original modulo 8
SUB ECX, EAX ;Get the "remainder"
MOV AL, 1 ;Set bit 0
SHL AL, CL ;Set bit [remainder]
MOV theMask, AL

; Now you can access the ith bit with:
MOV AL, [EDX + BitField]
TEST AL, theMask ;0 or 1?

Amiright? Totally untested.

BTW, his use of the term "vector" kind of made me chuckle. It's a $5 word that mathematicians use, where us ordinary folks would say "table" or "bitfield" or some other term. Vector? That's the kind of language one uses with one's nose in the air.
Assembly language programming should be fun. That's why I do it.


Quote from: NoCforMe on December 31, 2022, 03:42:57 PM
Quote from: jj2007 on December 23, 2022, 12:55:38 AM
Just in case you have nothing better to do :cool:

QuoteGiven a list of one million random 7-digit phone numbers write a program that prints a sorted list of the phone numbers with duplicates removed, using less than 2MB of memory and that runs in linear time

Interesting challenge, but can you explain what "runs in linear time" means? That's a term I'm not familiar with.

It means that if sorting 1000 items takes 1 millisecond, sorting 10000 will take ten milliseconds. Many sorting algos behave differently: they would take 100 milliseconds then. Try a bubble sort, for example.

It's irrelevant for small item counts below a few thousand, but once you have a Million to sort, you wish for "linear time" behaviour :cool: