pop = 0;Can we do better? Yes, according to Henry S. Warren, Jr., who wrote "The Quest for an Accelerated Population Count" of Beautiful Code. There are many ways to improve the loop. For example, if x is a small number, then the loop can be improved as followed.
for (i = 0; i < pop =" pop" x =" x">> 1;
}
pop = 0;The following is looped as many times as the number of 1-bit in x.
while (x) {
pop = pop + (x & 1);
x = x >> 1;
}
pop = 0;Or we can trade space for time. Look up the number of 1-bit in a table.
while (x) {
pop = pop + 1;
x = x & (x - 1); //turn off the rightmost bit
}
static char table[256] = {0, 1, 1, 2, 1, 2, 2, 3, ...,And several non-trivial approaches are discussed in the article. The author further applied the 'population count' functions to other problems, such as comparing population counts of two words, calculating Hamming distance, computing the number of trailing 0s in a word and allowing fast direct indexed access to a sparse array. Someone even posted performance analysis of the population count functions on the Internet. It seems Google would ask this kind of questions in an interview. Though I am not sure where I can apply the population count functions in my projects, Mr. Warren's article is definitely very informative.
pop = table[x & 0xFF] + table[(x >> 8) & 0xFF] + table[(x >> 16) & 0xFF] + table[x>> 24];
1 private void DemonstrateRowBeginEdit()
2 {3 DataTable table = new DataTable("table1");
4 DataColumn column = new5 DataColumn("col1",Type.GetType("System.Int32"));
6 table.RowChanged+=new7 DataRowChangeEventHandler(Row_Changed);
8 table.Columns.Add(column);9
10 // Add a UniqueConstraint to the table.11 table.Constraints.Add(new UniqueConstraint(column));
1213 // Add five rows.
14 DataRow newRow;15
16 for(int i = 0;i<5; i++)17 {
18 // RowChanged event will occur for every addition.19 newRow= table.NewRow();
20 newRow[0]= i;21 table.Rows.Add(newRow);
22 }23 // AcceptChanges.
24 table.AcceptChanges();25
26 // Invoke BeginEdit on each.27 Console.WriteLine(
28 "\n Begin Edit and print original and proposed values \n");29 foreach(DataRow row in table.Rows)
30 {31
32 row.BeginEdit();33 row[0]=(int) row[0]+10;
34 Console.Write("\table Original \table" +35 row[0, DataRowVersion.Original]);
36 Console.Write("\table Proposed \table" +37 row[0,DataRowVersion.Proposed] + "\n");
38 }39 Console.WriteLine("\n");
40 // Accept changes41 table.AcceptChanges();
42 // Change two rows to identical values after invoking BeginEdit.43 table.Rows[0].BeginEdit();
44 table.Rows[1].BeginEdit();45 table.Rows[0][0]= 100;
46 table.Rows[1][0]=100;47 try
48 {49 /* Now invoke EndEdit. This will cause the UniqueConstraint
50 to be enforced.*/51 table.Rows[0].EndEdit();
52 table.Rows[1].EndEdit();53 }
54 catch(Exception e)55 {
56 // Process exception and return.57 Console.WriteLine("Exception of type {0} occurred.",
58 e.GetType());59 }
60 }61
62 private void Row_Changed(object sender,63 System.Data.DataRowChangeEventArgs e)
64 {65 DataTable table = (DataTable) sender;
66 Console.WriteLine("RowChanged " + e.Action.ToString()67 + "\table" + e.Row.ItemArray[0]);
68 }
