Useful and Common bitwise operations in C

A collection of common and useful bitwise operations

To multiply by 2 power x
i = i << x

To set a bit in an integer:
number |= 1 << x;

To clear a bit in an integer:
number |= ~(1 << x);

To toggle a bit in an integer:
number ^= 1 << x;

To check a bit in an integer:
is_checked = number & (1 << x);

To count the number of set bits in an integer:
i &= i - 1; // will reset the right most set bit, loop until zero

Interview Screening Question

I received the following test as a screening step to a potential Software Engineer position. I thought it was pretty good compared to the type and nature of screenings you usually get in the Tampa Bay market.

Here it goes:

Implement the missing class without modifying the provided classes.
The correct output should be:
Local Boys = 6 (Home)
Tourists = 0 (Away)

 

using System;

namespace Test {
    public class FootballTeam : Team {
        public FootballTeam(string name, FieldAdvantage side)
            : base(name, side) {
        }

        public override int NumPlayers {
            get {
                return 11;
            }
        }

        public void Touchdown() {
            Score += 6;
        }
    }

    public class Game {
        public FootballTeam Home = new FootballTeam("Local Boys", Team.FieldAdvantage.Home);
        public FootballTeam Away = new FootballTeam("Tourists", Team.FieldAdvantage.Away);

        public static void Main() {
            Game game = new Game();
            Referee referee = new Referee(game);
            game.Home.Touchdown();
            game.Away.Touchdown();
            game.Home.Score += 100;
            Console.WriteLine("{0} = {1} ({2})", game.Home, game.Home.Score, game.Home.Side.ToString());
            Console.WriteLine("{0} = {1} ({2})", game.Away, game.Away.Score, game.Away.Side.ToString());
        }
    }

    public class Referee {
        public Referee(Game game) {
            game.Home.ScoreChange += new Team.ScoreChangeEventHandler(OnScoreChange);
            game.Away.ScoreChange += new Team.ScoreChangeEventHandler(OnScoreChange);
        }

        private void OnScoreChange(Team.FieldAdvantage side, int newScore, ref bool overrule) {
            if ((side == Team.FieldAdvantage.Away) || (newScore > 100))
                overrule = true;
        }
    }
}

ASP.NET MVC Model Binding Form Inputs To Action Parameters

The conventions followed by asp.net mvc for model binding are volatile to my brain for some reason.

Here is a summary of the different ways to bind input fields to action parameters.
Assuming the following class:

public class Person
{
    public string Name;
    public string Email;
}

Binding a Custom type

<%= Html.TextBox("Name") %>
<%= Html.TextBox("Email") %>

Will bind to:

public ActionResult MyAction(Person myPerson)
{
    // …
}

Binding a Custom type with parameter name prefix

<%= Html.TextBox("myPerson.Name") %>
<%= Html.TextBox("myPerson.Email") %>

Will bind to:

public ActionResult MyAction(Person myPerson)
{
    //…
}

Binding a Custom type with a custom prefix

<%= Html.TextBox("myPrefix.Name") %>
<%= Html.TextBox("myPrefix.Email") %>

Will bind to:

public ActionResult MyAction([Bind(Prefix = "myPrefix")] Person myPerson)
{
    // ...
}

Binding to Collections of Simple Types

<%= Html.TextBox("Name") %>
<%= Html.TextBox("Name") %>
<%= Html.TextBox("Name") %>

Will bind to:

public ActionResult MyAction(List<string> Name)
{
    // …
}

Binding to Collections of Custom Types

<%= Html.TextBox("myPerson[0].Name") %>
<%= Html.TextBox("myPerson[0].Email") %>
<%= Html.TextBox("myPerson[1].Name") %>
<%= Html.TextBox("myPerson[1].Email") %>

Will bind to

public ActionResult MyAction(List<Person> myPerson)
{
    //…
}

Binding to Dictionary of Custom Types

<%= Html.Hidden("myPerson[0].key", "keyOne") %>
<%= Html.TextBox("myPerson[0].value.Name") %>
<%= Html.Hidden("myPerson[1].key", "keyTwo") %>
<%= Html.TextBox("myPerson[1].value.Name") %>

Will bind to

public ActionResult MyAction(IDictionary<string, Person> myPerson)
{
    // …
}

Notes on MVC routes mapping

1. Add the more specific rules first and the more generalized ones at the end
2. Define defaults from the back to front
3. controller and action must exist in all rules either in the URL part or the default part. Otherwise the route handler won’t know what controller/action to map the URL to.

Things I’d love to learn more about

Below are some questions in various subjects I encounter either through day to day work or reading tech articles and blogs.

I will put the subjects in bullets and when i find the answers i will hyper-link them to another post where I write the answer I found.

• How exceptions are implemented by compilers? How does the assembly generated by the compiler look like?
• In public key cryptography, what is the algorithm used to raise very large numbers to very large exponents? I know it uses assembly to do bit manipulation but what is the exact algorithm.

If anyone can point me to some reference to fulfill my lust to learn about any of the subjects above, I’d appreciate it.

"Remember Me" Doesn’t work in ASP.NET

The "remember me" option in asp.net 2.0 will remember the user for as long as the Timeout period set in the forms authentication in the web.config

It’s really weird how it works as it is now. Below is an excerpt from a post found on the DotNukeForum:

How forms authentication cookies worked under asp.net 1.1

session cookies expiration = current datetime +the forms timeout value e.g. 60
persistent cookies expiration = current datetime + 50 years

 

How forms authentication cookies work under asp.net 2.0

session cookies expiration=current datetime +the forms timeout value e.g. 60
persistent cookies expiration= current datetime +the forms timeout value e.g. 60

Regex Inverse Matching

Came across a situation today were I need to inverse match on a string. In other words I want to match anything that is not xyz.

Here is how to do it using negative look-ahead:

^((?!xyz).+)$

Alternatively you can use negative look-behind:

^(.+(?<!xyz))$

On Defensive Programming

Notes from Code Complete

• Use error-handling code for conditions you expect to occur; use assertions for conditions that should never occur
• Use assertions to document and verify preconditions and postconditions
• Throw exceptions at the right level of abstraction; include all information that led to the exception
• Always have a mechanism to log application errors and a way to read that log.

Getting Around Dynamic Casting To Achieve Better Design And Performance

Using dynamic casts to determine an execution path in your code is not the best to write your logic.

I realized this fact while looking at Google’s style guide for C++

Do not use RTTI, except in unit-tests. If you find yourself in need of writing code that behaves differently based on the class of an object, consider one of the alternatives to querying the type.

Virtual methods are the preferred way of executing different code paths depending on a specific subclass type. This puts the work within the object itself.

If the work belongs outside the object and instead in some processing code, consider a double-dispatch solution, such as the Visitor design pattern. This allows a facility outside the object itself to determine the type of class using the built-in type system.

If you think you truly cannot use those ideas, you may use RTTI. But think twice about it. :-) Then think twice again. Do not hand-implement an RTTI-like workaround. The arguments against RTTI apply just as much to workarounds like class hierarchies with type tags.

That was an eye-opener to me. I didn’t know what double-dispatch is all about. Turns out that it’s the heart of the Visitor’s Pattern (although the example at dofactory.com is not ideal because they do not provide overloads for the visit() function and they cast all types to the base).

 

Double-Dispatch is the ability to dynamically select a method according to the run-time type of the caller (single dispatch) and the run-time type of the argument as well.

 

To close out, remember before you use dynamic casting in your code to think if there is a better way to achieve the same results using function overloads, virtual functions or double dispatch.

Parsing SQL Statements With Regex

I was trying to parse a SQL script the other day with regular expressions to extract some values of some columns. The script looked something like this:

NSERT INTO wp_posts (ID, post_author, post_date, post_content, post_title) VALUES (5, 1, ’2008-02-03 20:06:31′, ‘marco”s long text’, ‘hello world’);

so I had a regular expression that would capture anything between two apostrophes

‘(?<text>[^']+)’

The problem is escaped apostrophes in the text itself. Like in the example above marco”s long text it would stop at the first apostrophe.

So, in short,  to get around that, I did a simple ORing like this:

‘(?<text>([^']|[']{2})+)’

Seems very simple, but it took me a while to see the light.

My Favorite Geek Quotes

I think any of those would be cool to have on a T-shirt.

• I would love to change the world, but they won’t give me the source code
• There are 10 types of people, those who understand binary, and those who don’t
• There is no place like 127.0.0.1
• Oh, please, Give me a <br/>
• I’m not married, I’m only loosely coupled
• To understand recursion, you must first understand recursion
• Girls are like Internet domain names, the ones I like are already taken
• How many people can read hex if only you and dead people can read hex?

jscalendar shows at the top of the screen in IE7

jscalendar v1.0 has a bug that makes the calendar displays at the top of the screen in IE7.

Here is a patch that fixes it.

reference: http://drupal.org/node/118926

Platform-Independent Bitwise Rotation function

A simple macro to rotate the bits of an unsigned 32-bit value. using shift-left and shift-right we can achieve rotate-left and rotate-right.

#define rotlFixed(x,n) (((x) << (n)) | ((x) >> (32 - (n))))
#define rotrFixed(x,n) (((x) >> (n)) | ((x) << (32 - (n))))

The macro above can be trivially converted to a function and used in C# for example.

JavaScript font detector

I found this little JavaScript utility that tests for the existence of a specific font on the client machine.
I thought it would be very handy to use for my church’s website (coming soon) which will probably have some content written in the Coptic language.

Most probably we will be using Athanasuis font.

Anyways, I want to save the script here in case the original site goes down or something.

The script is released under Apache License, Version 2.0

You Suck At Photoshop

I stumbled on this series of youtube episodes at digg.com and I think they are amazing.

if you have a few minutes check them out. each episode is like 5 minutes long.

Here is episode #2 but definitely check out the other episodes as well in the related videos section.

Shuffling Analysis

This post is in regard to Jeff Atwood’s post on Shuffling and The Danger of Naïveté.

In his second post he used an example of shuffling three-card deck 600,000 times to explain how naive solutions can be dangerous. The post is extremely well written. I enjoyed every bit of it. However I had two questions that I couldn’t find an answer for in Jeff’s post. Why exactly 3 permutations (out of the 6 possible ones) are biased? and why those 3 specifically are biased and not any other permutations?

I spent sometime thinking about it and using a pencil and a paper I was able to get some answers.
First here is the naive method: (I reversed the loop to be as similar as possible to the correct method)

for (int i = cards.Length - 1; i >= 0; i--)
{
    int n = random.Next(cards.Length);
    Swap(ref cards[i], ref cards[n]);
}

And here is the correct one (Knuth Shuffle)

for (int i = cards.Length - 1; i > 0; i--)
{
    int n = rand.Next(i + 1);
    Swap(ref cards[i], ref cards[n]);
}

Now let’s agree on some facts real quick. For a three-card deck:

1. There are exactly 6 unique possible permutations for that deck (3!)
2. Using the Naive shuffling method, there are 27 possible sequences of random-numbers on any given run (3³)

The answer to the first question above, is that 27 mod 6 is equal to 3. What that means is there are 3 extra sequences of random numbers that have to map to 1 (or 2 or 3) of the 6 unique permutations of the deck.

To answer the second question we have to note something first about using swapping to perform a shuffle, take a look at the state of the deck at each iteration given the following random numbers:

Step Random Number Deck 0 N/A 123 1 2 132 2 3 123 3 3 321

Step Random Number Deck 0 N/A 123 1 1 321 2 1 231 3 2 321

Notice how the two different sequences of random-numbers resulted in the same permutation of the deck. Now remember there are 27 possible sequences and only 6 unique permutations. if we divide 27/6 we get 4 (with remainder 3) which means there are at least 4 paths (or sequences) for every unique permutation of the deck, the 3 extra possible sequence lead to 3 of the unique permutations giving them an advantage over the other 3.

so basically we have 6 permutations of the deck, 3 of them have 4 random-number sequences that lead to them, and the other 3 have 5 sequences that lead to them.

In this particular example if you follow the algorithm above and try the following random-number sequences you will get the same deck permutation for all 5.

• 1,1,2
• 3,1,3
• 2,2,2
• 1,3,1
• 2,3,3

Conclusion

The problem with the Naive shuffling method is swapping! The fact that swapping elements in 2 (or more) different sequences can lead to the same deck permutation is a subtle problem.

The Knuth shuffle algorithm avoids that problem by ensuring N! possible random sequences where N is the number of elements in a deck (or any container).

Function Pointers

Declaring function pointers in C\C++ has a somewhat strange syntax, specially when you want to specify a function pointer as the return type of another function.
so here is a brief explanation:

To declare a pointer to an int called pNumber:

int *pNumber;

To declare a pointer to a function called pFunc (that has a string parameter and returns an int):

int (* pFunc)(string);

in red is the variable name, in purple is the type.

To declare a function that returns a pointer to a function:

int (* GetFuncPointer(void) )(string);

in red is a normal function declaration, in purple is the return type of that function.
S o basically int(*)(string) is the type of the function pointer.

If we want to declare a function that takes a function pointer as a parameter then we would write something like this:

void RegisterCallBack( int(*)(string) ); /* unnamed parameter */

or

void RegisterCallBack( int(*myCallback)(string) ); /* named parameter */

A prettier way to use function pointers is to use typedef to declare an alias. The typedef syntax is exactly the same as declaring a regular variable (or a function pointer).

typedef int(*FunctionPointer)(string);

now we can use FunctionPointer like this:

FunctionPointer GetFuncPointer(void);

Click For More Information…

Mr. Compiler, would you please inline this function?

I’ve always read that marking a function inline doesn’t guarantee that the compiler will actually inline it, but it’s merely a hint to the compiler to “try its best” to do it. Which have always raised the question in my head, how do I know if Mr. Compiler agreed to inline my function? Do I have to look at the generated assembly code? There has to be an easier way!

So I invested 15 minutes researching that issue and found out that Mr. Compiler is friendly enough to let you know if it was not possible to fulfill your request to inline a certain function by issuing a warning.

For Microsoft’s VC8 compiler warning C4710 is turned off by default, you can turn it on by doing any of the following (depends on your choice):

1. #pragma warning (default : 4710)
2. #pragma warning (custom_warning_level : 4710)

For GCC the -Winline switch can be used to achieve the same thing.

Installing nVidia drivers on debian linux

Since I forget the steps every single time I try to install or upgrade linux I’ll write them down.

1. download the drivers from www.nvidia.com (usually a file with .run extension)
2. download the kernel header files — apt-get install linux-headers-$(uname -r)
3. execute the command — sh path to the nvidia driver here

There is another method I found, that seems to work for a lot of people:

1. apt-get install module-assistant
2. m-a prepare
3. m-a auto-install nvidia

‘Developers’ Anagrams !!!

I’m a big fan of anagrams, they are very interesting to me, they are mysterious, funny and sometimes true..

quoting a phrase on my favorite anagram generator site “All the life’s wisdom can be found in anagrams. Anagrams never lie.”

here are a few interesting anagrams for the word developers:

• Peeve Lords (that’s us for the customers)
• Deep Solver
• Speed Lover (for the performance obsessed ones)
• Deep Lovers

Anagrams are amazing..