Everybody needs a bit of help, here are 32

  • (2 Pages)
  • +
  • 1
  • 2

16 Replies - 3723 Views - Last Post: 16 January 2013 - 06:44 AM

#1 BetaWar  Icon User is offline

  • #include "soul.h"
  • member icon

Reputation: 1184
  • View blog
  • Posts: 7,254
  • Joined: 07-September 06

Everybody needs a bit of help, here are 32

Post icon  Posted 04 January 2013 - 01:00 PM

*
POPULAR

What can you do in 32 bits?

This is just a fun little game to see what you can represent in a standard 32-bit integer. As most (all?) languages allow for bitwise operations I don't care what language you program it in (or even if you program up your example). The rules are very simple: You have 32-bits of space to use. Make good use of them.

What I would like to see from you:
What you would store in the bits, what they represent, and how this is useful.

Example:
Storing a date string in an 4 bytes.
20130104 or YYYYMMDD (8 bytes in total) can be compressed down to, at most, take up 4 bytes. Here's how:
You cannot accomplish standard huffman encoding of the characters as the data required to rebuild the huffman tree would be larger than 4 bytes, however if you create a standard huffman tree that will be used by everyone, then you don't need to store tree-construction information in the data you are sending back and forth. By running a frequency count of the numbers 1 through 31 (days of the month) all concatenated together in a string (no spaces) you can construct the huffman tree like so:
   /      \
  / \     /  \
 /\ /\   /\  /  \
1 2 3 0 4 6 /\  /\ 
           7 8 9  5


Where left is a 0, and right is a 1 (bit value). At that point you have 4-bits to get to 7, 8, 9, and 5, and 3-bits for 1, 2, 3, 4, 6, and 0. If you have the date 9999 88 77 (not a valid date, I know) that would be: 1110 1110 1110 1110 1101 1101 1100 1100, which is 32 bits in total. This date format is also good until the year 10,000 for an added bonus.

So, what can you do with 32-bits?

Is This A Good Question/Topic? 5
  • +

Replies To: Everybody needs a bit of help, here are 32

#2 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2068
  • View blog
  • Posts: 4,301
  • Joined: 11-December 07

Re: Everybody needs a bit of help, here are 32

Posted 04 January 2013 - 02:36 PM

Remember Spirograph?
https://www.google.c...s&tbm=isch&sa=X

You have a cog with holes at various radii. Put it inside a larger circle and by drawing you get some fancy curves. Draw with different cogs and choosing different holes and you can build up quite a nice pattern.

If you don't know what I'm talking about, check out the link. ;)

You can represent all this by two relative sizes. Let's take 4 bits for each size (sounds like hex!) The first number is the radius of the hole as a fraction of the size of the disc (in fifteenths). The second number is the size of the disc as a fraction of the size of the outer circle (also in fifteenths).

Because you only need a byte for each pattern, you can build up pictures using up to 4 patterns if they share the same outer circle. I'm torn between 4 monochrome patterns or 3 patterns and some colour information.

With a spare byte you have 256 different colour combinations. With a pallet of 12 colours, the nCr formula says there are 220 combinations (i.e. less than 256). This means you could use a lookup table to allow the choice of 12 colours.
Was This Post Helpful? 2
  • +
  • -

#3 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1623
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: Everybody needs a bit of help, here are 32

Posted 04 January 2013 - 03:05 PM

Bit boards are pretty cool. In just 32 bits you can represent all pieces of a certain type in a checkers game. there are 4 types however, black regular, black king, red regular, red king. I used this representation to make a checkers AI once.
Was This Post Helpful? 2
  • +
  • -

#4 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2270
  • View blog
  • Posts: 9,496
  • Joined: 29-May 08

Re: Everybody needs a bit of help, here are 32

Posted 05 January 2013 - 02:23 AM

BetaWar 32bits for date YYYYMMDD ??!

You only require 9 bits for the day of the year 366
Or more precisely.
366 = 2 ^ x
  x = log(366) / log(2)
  x = 8.5157 (bits)



So the bit pattern is now m mmm.d dddd, if we use 16bits (7 bits) we can play with a 128 year range.
Or with a little math we can stretch that to a 179(7.483bits) year range.

yy = value \ 366; */ YEAR  /*
yr = value % 366;
mm = yr \ 31;     */ MONTH /*
dd = yr % 31;     */ DAY   /*



So the bit pattern is now yyyy yyy.ym mmmm.d dddd

Or we use 32bits (23.483) bits to play with) for the year.
yyyy yyyy yyyy yyyy yyyy yyy 8,388,608years (or with math hack 8,388,659)
Was This Post Helpful? 0
  • +
  • -

#5 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2068
  • View blog
  • Posts: 4,301
  • Joined: 11-December 07

Re: Everybody needs a bit of help, here are 32

Posted 05 January 2013 - 04:36 AM

If you are storing the day from 0-365 and the year then you don't need to store the month. The only complicated part in determining it algorithmicly is working out if its a leap year.
Was This Post Helpful? 0
  • +
  • -

#6 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3116
  • View blog
  • Posts: 19,153
  • Joined: 14-September 07

Re: Everybody needs a bit of help, here are 32

Posted 05 January 2013 - 04:16 PM

IPv4 addresses: 255.255.255.255 can be represented by an unsigned 32 bit integer
Was This Post Helpful? 0
  • +
  • -

#7 BetaWar  Icon User is offline

  • #include "soul.h"
  • member icon

Reputation: 1184
  • View blog
  • Posts: 7,254
  • Joined: 07-September 06

Re: Everybody needs a bit of help, here are 32

Posted 07 January 2013 - 09:26 AM

AdamSpeight2008 - I was just giving a simplistic example above. There are a number of better formats to store dates in. I like your, and had actually come up with a very similar one:
9 reserved bits
14 bits for the year
4 bits for the month
5 bits for the day of month
OR you could move the 9 reserved bits to the year field and have 23 bits for the year.
Was This Post Helpful? 0
  • +
  • -

#8 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2068
  • View blog
  • Posts: 4,301
  • Joined: 11-December 07

Re: Everybody needs a bit of help, here are 32

Posted 08 January 2013 - 08:05 AM

Does nobody have more inventive ideas? How about the entire game state for a game of pong?

1 byte for each of the paddles and 2 bytes for the x and y coordinates of the ball.
Was This Post Helpful? 0
  • +
  • -

#9 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5905
  • View blog
  • Posts: 12,808
  • Joined: 16-October 07

Re: Everybody needs a bit of help, here are 32

Posted 08 January 2013 - 10:16 AM

You could fit the entire state of a tic-tac-toe board in 32 bits. The board itself is 18 bits, 2 bits for 00 none, 01 player1, 10 player2. With 4 more bits you can hold the turn. Leaving more than enough to hold winning state...

If you use three bits, you can also flag the winning path, leaving only 5 bits. If you hold the turn, you have 1 bit left, which can tell you if the game is still being played. From the turn and the playing flag, you can determine the winner or a draw.

Actually, since you can determine the winning player from turn, you could still just use 2 bits for position, designating the path with 11. 32 is way too big for tic-tac-toe. :P

You can use 6 bits for a position on a chess board, 3 bits for the piece, so 32 bits could be two chess pieces, their position, and the ranking of that position.
Was This Post Helpful? 1
  • +
  • -

#10 BetaWar  Icon User is offline

  • #include "soul.h"
  • member icon

Reputation: 1184
  • View blog
  • Posts: 7,254
  • Joined: 07-September 06

Re: Everybody needs a bit of help, here are 32

Posted 08 January 2013 - 12:07 PM

Go-fish with a standard 52-card deck can be represented in 26-bits (13 cards, 4 suites, 2 matches per card). This is done by counting from 0 (A) through 12 (K) and having 2 bits for each card:

00 00 00 00 00 00 00 00 00 00 00 00 00
A  2  3  4  5  6  7  8  9  10 J  Q  K



Each of the two-bit groups represents a match in that group (since there are only 4 of each card you can only have 2 matches). Then you can use the next 6 bits to represent how many people are playing, and whose turn it is (3 bits each, with a max of 7 players - which is likely overkill for only 52 cards...)

---------------
Velocity, direction and position (longitude and latitude)

8-bits: velocity (allowing for 255 MPH max speed, which is more than most cars are supposed to go/ peg out on)
3-bits: direction (N = 000, NE = 001, E = 010, SE = 011, S = 100, SW = 101, W = 110, NW = 111)
8-bits: latitude from -90 to 90, as an integer
9-bits: longitude from -180 to 180, as an integer
4-bits: free space!
Was This Post Helpful? 1
  • +
  • -

#11 BetaWar  Icon User is offline

  • #include "soul.h"
  • member icon

Reputation: 1184
  • View blog
  • Posts: 7,254
  • Joined: 07-September 06

Re: Everybody needs a bit of help, here are 32

Posted 10 January 2013 - 01:03 PM

A fun little challenge for those of you interested: How do you store a hot lady's (or guy's) phone number in 32-bits?

There is the obvious lookup table, but that isn't very interesting; so other solutions?
Was This Post Helpful? 0
  • +
  • -

#12 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2068
  • View blog
  • Posts: 4,301
  • Joined: 11-December 07

Re: Everybody needs a bit of help, here are 32

Posted 10 January 2013 - 04:54 PM

For a UK mobile number, they all start with 07 and then have 9 variable digits. It's not much of a challenge to store 9 digits in a uint32. ;)
Was This Post Helpful? 0
  • +
  • -

#13 BetaWar  Icon User is offline

  • #include "soul.h"
  • member icon

Reputation: 1184
  • View blog
  • Posts: 7,254
  • Joined: 07-September 06

Re: Everybody needs a bit of help, here are 32

Posted 11 January 2013 - 10:21 AM

Lol, alright, but when dealing with the standard US number, which is 10 digits, it gets to be more fun.
Was This Post Helpful? 0
  • +
  • -

#14 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2270
  • View blog
  • Posts: 9,496
  • Joined: 29-May 08

Re: Everybody needs a bit of help, here are 32

Posted 12 January 2013 - 02:25 PM

Not possible since it requires
bits = log(10 000 000 000)
       -------------------
             log(2)
bits = 33.2192809...



34 bits minimum. You could squeeze in 9.6 digits in.

If there are restriction on what particular digits can be, may be you could squeeze it down
Was This Post Helpful? 0
  • +
  • -

#15 BetaWar  Icon User is offline

  • #include "soul.h"
  • member icon

Reputation: 1184
  • View blog
  • Posts: 7,254
  • Joined: 07-September 06

Re: Everybody needs a bit of help, here are 32

Posted 14 January 2013 - 02:06 PM

That is correct, we are trying to squeeze 10 billion values into something that can hold 4. I was thinking about trying to compress it in some way, but have been unable to come up with anything simple as of yet. I also thought about using a lookup table for the first 3 digits (area code) since there are something like 260 area codes in the US, and an additional 29 in Canada, but in the first post (above) I said that lookup tables where out...
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2